1
$\begingroup$

On an array of $n = 2^k$ numbers, where $k$ is a non-negative integer, the $k = \log n$ order statistics $1, 2, 4, 8,\ldots, 2^k$ can all be determined in a total of $Θ(n)$ time in the worst case.

I think that this statement is wrong because the loop will take $k$ iterations. So, the time should be $Θ(\log(n))$. But, I'm not sure my guess is correct. Could you tell me whether or not my guess is correct?

$\endgroup$
1
$\begingroup$

You can find all of these order statistics in $O(n)$. First, find the maximum (order statistic $2^k$) in time $O(n)$. Then, find the median (order statistic $2^{k-1}$) in time $O(n)$, and remove all larger elements. Find order statistic $2^{k-2}$ in time $O(n/2)$, and remove all larger elements. And so on. The total running time is $$O(n + n/2 + n/4 + \cdots) = O(n).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.