in Algorithms retagged by
1,016 views
0 votes
0 votes
How will you perform asymptotic comparison of the following three functions:

​1. $\log{n}$,

2. $(\log{n})^c$ and

3. $\sqrt{n}$

Obviously $\log{n} < (\log{n})^c$. But where $\sqrt{n}$ fits?​
in Algorithms retagged by
1.0k 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.

by

4 Comments

You can use a trick as long as you know the issues with it. In your answer you compared the functions for equality (not asymptotic equality) and so you got 1 < 2, which is correct here. But the same method goes wrong for the case I had given. Taking log is good way in GATE -provided one knows the issues also.
1
1
edited by
if $f_1=2\times \log{n}$ and $f_2=3\times \log{n}$, doesn't that translate to $f_1=O(f_2)$, (that is $n^2=O(n^3)$?) I understand both $f_1$ and $f_2$ are individually $O(\log n)$, but when compared to each other, I guess we can clearly see that $f_1=O(f_2)$ (which is equally obvious even from $n^2$ and $n^3$) So log approach seems not to lead to wrong conclusion. Isnt it?
0
0
can you write $f_2 = O(f_1)?$
0
0
1 vote
1 vote
$\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)
by

Related questions