Why Does the Deterministic Selection Algorithm Run in $O(n)$ and not $O(n\log n)$?

Question

Here is pseudocode for the algorithm:

select(L,k)
{
if (L has 10 or fewer elements)
{
    sort L
    return the element in the kth position
}

partition L into subsets S[i] of five elements each
    (there will be n/5 subsets total).

for (i = 1 to n/5) do
    x[i] = select(S[i],3)

M = select({x[i]}, n/10)

partition L into L1<M, L2=M, L3>M
if (k <= length(L1))
    return select(L1,k)
else if (k > length(L1)+length(L2))
    return select(L3,k-length(L1)-length(L2))
else return M
}

Here is some analysis of the algorithm: http://www.ics.uci.edu/~eppstein/161/960130.html

The analysis suggests to use the recurrence relation $T(n) \leq \frac{12n}{5} + T(\frac{n}5) + T(\frac{7n}{10})$. Solving this we get linear work for a call. But aren't there log many recursive calls? So that would be $n\log n$.

Put another way, conceptually this algorithm seems like it could be described as "for each call, cut the search area kind of like binary search, but not guaranteed to cut the search area by as much as binary search, and add a linear time partition". Binary search runs in $O(\log(n))$, so adding a linear search per call would make it $O(n\log(n))$.

What am I not understanding about the linked analysis?

Answer 1

Consider the following series

$S = n + \lceil n/2 \rceil + \lceil n/4 \rceil + ... + 1$

There are $\lceil \log_2 n \rceil + 1$ terms but the sum is less than $2^{\lceil \log_2 n \rceil+1} < 4n$ always.

Similarly, in your algorithm even though you have $\log n$ recursions, each recursion successively does a fraction of work. Hence the total work done in linear in $n$, rather than $\Theta(n \log n)$ as the naive analysis suggests, just similar to the sum of the series above. '

Also note that $T(n)$ is $O(n)$ as well as $O(n\log n)$. This is because $O(n\log n)$ is also an upper bound to $T(n)$ and therefore it is incorrect to say, for example, "Why is $T(n)$ not $O(n\log n)$?".