I was reading my textbook when I came across this example 
I was wondering how they got 35n^3 since we have log(n)?
Asked
Active
Viewed 39 times
0
-
2Because $\log n \leq n$ for $n\geq 1$. – trancelocation Mar 23 '21 at 06:01
-
@trancelocation so did they just yeet logn and went 20n^3 + 10n^3 + 5n^3? – Turkey Mar 23 '21 at 06:04
-
1Exactly. After replacing $\log n$ by $n$, they replaced all powers by $n^3$. The sum of the coefficients gives $35$. – trancelocation Mar 23 '21 at 06:05
-
@trancelocation I see, thank you! – Turkey Mar 23 '21 at 06:06
-
You are welcome. – trancelocation Mar 23 '21 at 06:06
1 Answers
1
In fact, $\color{red}{\log n<n}$ for all $n>1$, so $20n^3+10n\log n+5<20n^3+10n^2+5$, and $n^2<n^3,1<n^3$, so $10n^2<10n^3$, $5<5n^3$, so $20n^3+10n\log n+5<20n^3+10n^2+5<20n^3+10^3+5n^3=35n^3$.
Given $f(x)=x-\log x$, then $f^{'}(x)=1-\frac{1}{x}$, so when $x>1$, $f^{'}(x)>0$, so $f(x)$ increase on $(1,\infty)$, and $f(x)>f(1)=1$ for $x\in (1,\infty)$. As for the case in $\mathbb{N}$, we always have $n\geq1$, so $\color{red}{n>\log n}$.
UESTCfresh
- 622