How to show that $O(n^\frac{3}{4} \log n) = O(n)$?

Question

I try to analyze LazySelect algorithm (finds kth order statistic of a set). One of the steps is to take a sample of $n^\frac{3}{4}$ elements and sort it. It seems like this sorting is linear relative to original size $n$.

How to show that $O(n^\frac{3}{4} \log n) = O(n)$?

I was trying to show that for some large n: $\frac{n}{\log n} \ge n^\frac{3}{4}$ but don't know how to do it.

Answer 1

Since for all $a,b > 0$ we have $(\log n)^{a} = o(n^{b})$ as $n$ grows, so $n^{1/4} > \log n$ for large $n$, i.e. $n > n^{3/4}\log n$ for large $n$. If $f(n) = O(n^{3/4}\log n)$ as $n \to \infty$, then there is some $M \geq 0$ such that $|f(n)| \leq Mn^{3/4}\log n < Mn$ for large $n$, so $f(n) = O(n)$.

Answer 2

Very simple : you even have more: it is standard that $n^\alpha\ln^\beta n=o(n^{\alpha'}\ln^{\beta'}n)$ as soon as $\alpha<\alpha'$. Just apply these rules of Asymptotic analysis:

• if $f=o(g)$, then $O(f)=o(g)$,
• if $f=o(g)$, then $f=O(g)$.