How can one show that $n \log n \subseteq O(n^{1+\epsilon})$ where $0 < \epsilon < 1$ without using limits? This question arise from a homework where I used limits to prove the relation. I'd like to know if there is another way.
Proving $n \log n \subseteq O(n^{1+\epsilon})$ without limits
6
$\begingroup$
asymptotics
-
0A bit nitpicky: I suggest either saying $\epsilon$ is fixed, or writing the above as $n\log n=O_\epsilon \left(n^{1+\epsilon}\right)$ to indicate the constant depends on $\epsilon$. (Otherwise it is simply not true) – 2011-09-17
1 Answers
6
Let $0<\epsilon<1$ be fixed. We need only show that $\log n=O(n^\epsilon)$. Suppose $n\geq 1$ so that $\log n\geq 0$. Since $$n^\epsilon=e^{\epsilon \log n}=1+\epsilon \log n+\frac{\epsilon^2 \log^2 n}{2}\cdots \geq \epsilon \log n$$ we see that $$\log n \leq \frac{1}{\epsilon}n^\epsilon $$ which proves the desired result.
-
0Why couldn't you stop the expansion at $\epsilon \log n$? – 2011-09-17
-
0@Pho: Huh. You could! Great idea. I edited accordingly. – 2011-09-17
-
6Instead of expanding into a series you could use the inequality $e^x \geq 1+x$. – 2011-09-17