Why Does the Deterministic Selection Algorithm Run in $O(n)$ and not $O(n\log n)$?
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} &lt; 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)$?".