0
$\begingroup$

This was one of the previous year's exam questions. I have to order the following functions according to their growth rates using the $\mathcal O(n)$ notation.

$f_1(n) = 2010 * \log_3(n^n)$

$f_2(n) = n^{1+2+...+ \log_2 \log_2 n }$

$f_3(n) = 4^{100+\log_2 n}$

How do I deal with these kind of problems?

1 Answers 1

2

First you forget about all multiplicative constants. We are left with $ \log (n^n) \quad n^{\sum_{i=1}^{\log_2\log_2 n} i} \quad 4^{\log_2 n} $ Now you simplify all the terms: $ n\log n \quad n^{\Theta(\log_2\log_2 n)^2} \quad n^2 $ In principle you can first calculate the exact sum in $f_2$, but here it really doesn't matter. Now let's look at all the exponents of $n$: $ 1+o(1) \quad \Theta(\log_2\log_2 n)^2 \quad 2 $ The $o(1)$ term is all that remains of the logarithm. Some other exercise might require comparison of such terms, but here we need not be so exact. The ordering is now clear: $1+o(1) < 2 < \Theta(\log_2\log_2 n)^2.$ So $f_1 \ll f_3 \ll f_2$.