2.35

Dominant terms giving [math]\Theta[/math]-equivalents
1. [math]f_1(n)=1000\cdot2^{n}+4^{n}\quad\Longrightarrow\quad4^{n}\text{ dominates}\;\Rightarrow\;f_1(n)=\Theta(4^{\,n})[/math].
2. [math]f_2(n)=n+n\log n+\sqrt n\quad\Longrightarrow\quad n\log n\text{ dominates}\;\Rightarrow\;f_2(n)=\Theta(n\log n)[/math].
3. [math]f_3(n)=\log(n^{20})+(\log n)^{10}=20\log n+(\log n)^{10}\quad\Longrightarrow\quad(\log n)^{10}\text{ dominates}\;\Rightarrow\;f_3(n)=\Theta\!\big((\log n)^{10}\big)[/math].
4. [math]f_4(n)=(0.99)^n+n^{100}\quad\Longrightarrow\quad (0.99)^n\!\to0\text{ while }n^{100}\to\infty\;\Rightarrow\;f_4(n)=\Theta(n^{100})[/math].

Back to Chapter 2