3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Rather than cross-posting, in the future I encourage you to migrate your question. You can do that by clicking the "flag" button and marking the post as needing moderator attention, and asking the moderator to migrate your post. This helps us avoid duplicates scattered across multiple sites. $\endgroup$ – D.W. Sep 15 '13 at 5:37
  • $\begingroup$ Thanks for the tip D.W. I deleted my original post when I reposted here, so I thought that would eliminate the duplication. $\endgroup$ – faora Sep 16 '13 at 0:08
6
$\begingroup$

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

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