The definition:
given two functions $f$ and $g$, $f(n)$ is in the class $O(g(n))$ if there exist constants $N$ and $c$ such that $f(n)<c ⋅ g(n)$ when $n > N$.
Asked
Active
Viewed 142 times
-1
GNUSupporter 8964民主女神 地下教會
- 17,627
reuseman
- 129
-
Possible duplicate of prove $n$ is $O(n\log n)$ – Jan 11 '18 at 16:12
-
@Rohan The question writer of the linked question asked for help when proving this by limits. Here, OP asks for a proof using the definition, so IMHO, it's not an exact duplicate. – GNUSupporter 8964民主女神 地下教會 Jan 11 '18 at 16:18
1 Answers
0
Hint:
When $N\ge3$, for all $n\ge N$, $\log n\ge\log N >1$, so $n < n \log n$ whenever $n > N$.
GNUSupporter 8964民主女神 地下教會
- 17,627
-
-
$\log N>1 \iff N > e \Leftarrow N \ge \lfloor e \rfloor + 1$ – GNUSupporter 8964民主女神 地下教會 Jan 11 '18 at 16:39