Kth largest element in an unsorted array 12.11 qstn in C++ book

#1

The O(n) solution provided breaks arrays into two equal halves at each step
with recurrsive formulae for time complexity be
T(n) = O(n)+T(n/2)

which gives a general formulae of
T(n) = (k*O(n))+T(n/(2^k))

evaluating time complexity of O(nlog n)

Am I correct???
If thats the case Qstn No 11.8 finding K closest elements to the median in O(n) time uses this same solution is also wrong?

0 Likes
#2

Hey @vinayak_sangar,

I don’t get why you get the general formula of T(n) = (k*O(n))+T(n/(2^k)) because the formula is T(n) = O(n)+T(n/2) in fact. You only need to solve T(n) = O(n)+T(n/2) which will give you T(n) = O(n).

Let me know if you have any problem.

0 Likes