Part A) Consider the general problem of finding the median of n entries. This ti
ID: 3873869 • Letter: P
Question
Part A) Consider the general problem of finding the median of n entries.
This time, it's also OK to scramble the array items while searching.
We might attempt to adapt the basic idea in the Quicksort routine to solve
this problem. Explain how to change the quickSort() code on Page 160 to find
the median; of course, for full credit you should eliminate unnecessary work
wherever possible. For simplicity, YOU MAY ASSUME THAT n IS ODD (so that
the the definition of 'median' is unambiguous).
Explanation / Answer
The worst case time complexity for the partition function will be O(2n).
The worst case time complexity will arise in case of a presorted array in which case thw loop condition will hold true for all iterations.