Randomized Median Element Algorithm in Mitzenmacher and Upfal: O(n) sorting step?

In the last section of chapter 3 (page 54) in Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the median of a set $S$ of distinct elements in $O(n)$ time. As a substep the algorithm requires sorting a multiset $R$ of values sampled from $S$, where $|R| = \lceil n^{3/4} \rceil$. I'm sure this is a fairly simple, and straight forward question compared to the others on this site, but how is sorting a multiset of this size bounded by $O(n)$?

I assume the algorithm is using a typical comparison-based, deterministic sorting algorithm that runs in $O(n\log$ $n)$. So, If I have the expression $O(n^{3/4}\log(n^{3/4}))$, isn't this just equivalent to $O(\frac{3}{4}n^{3/4}\log(n)) = O(n^{3/4}\log(n))$? How does the reduction down to $O(n)$ proceed?

Your analysis is correct, and you can conclude that $O(n^{3/4} \log(n)) = O(n)$ immediately. By L'hopital's rule $\log(n) = o(n^c)$ for any fixed $c > 0$, and in particular for $c = 1/4$. Therefore $O(n^{3/4} \log(n)) = O(n^{3/4} n^{1/4}) = O(n)$.

StackExchange Computer Science Q#14296, answer score: 6