CODEWITHSUNDEEP
algorithm
monkey
monkey

Reputation: 591

Algorithms-Asymptotic Notations

As I have read in book and also my prof taught me about the asymptotic notations

The general idea I got is,when finding asymptotic notation of one function w.r.t other we consider only for very large value of n.

So from here my confusion is-

2^n=O(3^n) and log2(n)=Θlog3(n)

First relation is clear to me and second relation is confusing me.Though I derived log2(n) and log3(n) to same base and noticed that log2(n)=log10(n)/log10(2) and log3(n)=log10(n)/log10(3) So In both constant factor can be removed.So second relation is also OK.

Still there remain a doubt that when I see the graph plot of log2(n) and log3(n). log2 is always above log3 and grows faster than log3 i.e the difference of log values increases as n increases. Then I got more confused when I saw the graph plot of x1=y and x2=2y in which again x2 is above x1 and difference is increasing b/w them as y increases.

So now I want to know .How do I distinguish from graph about the asymptotic relations of the function. In what sense they say one function is upper bounded by the other though 2 lines with different slopes also following this.Why don't we say one line is upper bounded by the other.We only say they are related by Θ.

Please help me understand this concept.

Upvotes: 1

Views: 170

Answers (1)

Henry
Henry

Reputation: 43728

The interesting question is not if one function has a larger value than the other but if it grows faster (always only looking at large enough n). For example, take f1=n2 and f2=100n2. f2 is always 100 times larger than f1 but if you compare f1(10) and f1(20) you see that that the latter value is 4 times the first. Exactly the same happens with f2(10) and f2(20), again a ratio of 4.

Therefore, these two functions grow in exactly the same way.

Upvotes: 1

Related Questions