1
$\begingroup$

$T_{3}=\Theta(n^{0.99}),\quad T_{2}=\Theta(n^{\log\log n}),\quad T_{1}=\Theta \left(\frac{n}{\log n}\right)$

I need to decide what is the relation (ratio?) between $ T_{1},\, T_{2},\, T_{3}$?

So by taking $\log$ on the three of them I came to conclusion that $ T_{3}>T_{1},\,T_{2}$.

$\log T_{3}=0.99n$, $\log T_{2}=(\log\log n)\log n$ and $\log T_{1}=\log n-\log\log n$

What do you think?

Thanks

  • 0
    @Nir: nope. $\log T_3$ should be $0.99 \log n$.2011-07-09

1 Answers 1

2

Your idea with the log is correct. However, you took the log of $T_3$ incorrectly. Given the functions $T_1$, $T_2$, and $T_3$, you know that (taking the log of the definition of the $\Theta$-notation) $ \log n - \log\log n + c_1 \leq \log T_1 \leq \log n - \log\log n + C_1,$ $ (\log\log n) \log n + c_2\leq \log T_2 \leq (\log\log n) \log n + C_2,$ $ 0.99 \log n + c_3\leq \log T_3 \leq 0.99 \log n + C_3,$ for $n> n_0$.

For $n$ large, $\log \log n> 1 > 0.99$ and thus $T_2> T_1 > T_3$.