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?

Improve this question
$\endgroup$
2
  • $\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. ♦
    Commented Sep 15, 2013 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
    Commented Sep 16, 2013 at 0:08

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.