# Computing order statistics $1,2,4,8,\ldots,n$

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?

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).$$