This problem asks you to determine bestcase and worstcase ti

This problem asks you to determine best-case and worst-case time complexities of given algorithms. (a) Consider the following method that computes the median of an array of consisting of distinct integers Input: Array a of size n. Assume that array has distinct elements. for i in [0 n-1] r 0; for j in [0, n-1] t if Ca Cj] x) r++; if r equals n or (n-1)/2 return x; Determine the best-case and worst-case time complexities of this algorithm using big-oh notation. Provide a justification for your time-bounds. For a given array of size n, what is the best-case input? For a given array of size n, what is the worst-case input?

Solution

(a)

The middle value in a sorted sequence of numbers is called median.

Therefore, the best-case time complexity is O(n) and the best-case input is the array having median in the first location.

Therefore, the worst-case time complexity is O(n^2) and the worst-case input is the array having median in the last location.

(b)

In the given code, basic operation is checking whether m is divisible by i or not(i.e, if (m % i == 0))

Since each integer is of size n-bits, division of two integers(m % i) takes O(n^2) time.

Therefore , best case happen for even numbers and best case run time is O(n^2).

Therefore the worst case happens for prime numbers and the worst case run time is also O(n^2).