retagged by
1,486 views

2 Answers

5 votes
5 votes

What I usually do to compare asymptotic is, I will keep taking log of all the functions, unless and until it will be easy to compare. For example think of the above problem

1) log n  --> After taking log it will be --> log log n

2) (log n)^c --> after taking log it will be --> c log log n

3) SQRT(n) --> after taking log it will be --> (1/2) log n

Now you can see very clearly that (1) < (2) < (3)

The beauty of this method is that you can apply this to each and every function.

1 votes
1 votes
$\sqrt {16} = 4$, $\lg_2 16 = 4$,
$\sqrt {1024} = 32$, $\lg_2 1024 = 10$.

So, $\lg$ is growing at a much lower rate $\implies \log n = o(\sqrt n).$ (small o)

Related questions

0 votes
0 votes
1 answer
2
0 votes
0 votes
0 answers
3
usdid asked Apr 16, 2022
267 views
a) what is the iterative equation showing the running time of the algorithm whose pseudocode is given below? b) What is this repeated equation in asymptotic notation usin...
2 votes
2 votes
2 answers
4
Sankaranarayanan P.N asked Jun 4, 2015
2,183 views
arrange the following in the increasing order of their asymptotic complexity in big theta notation$2^{2^{n}}, \log n ^{\log n} , (\frac{3}{2})^{n}, 2^{n}, \log n!$