2

2^n is the order of 3^n.

These two functions are related as 2^n = O(3^n).

or more appropriately , we can say 2^n = o(3^n).

I am having this doubt that what is actually the order. Is it saying same aymptotic order?

Wikipidia, big O notation says, that these two functions dont have the same order.

Plz, clarify me, what is actually order here.

I am new to algorithms, so plz correct me, if what i am asking is silly question.

Garrick
  • 677
  • 4
  • 15
  • 34
  • 3
    Possible duplicate of [What is a plain English explanation of "Big O" notation?](http://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) – interjay Aug 05 '16 at 10:19
  • @interjay, What is the meaning of order here ?? – Garrick Aug 05 '16 at 10:34

2 Answers2

5

Big-O is an upper bound. It basically says 2^n does not grow faster than 3^n, which is true.

Arguably, the meaning of the colloquial 'is in the order of' is closer to another Landau symbol, the Big-θ, which is both an upper and lower bound.

2^n is not an element of θ(3^n), as 3^n grows significantly faster.

ComicSansMS
  • 51,484
  • 14
  • 155
  • 166
  • 1
    Very good explaination . 2^n = O(3^n) and 2^n != omega(3^n). Hence, we can say 2^n != theta(3^n) . IS it right. ? – Garrick Aug 05 '16 at 11:49
  • @Willturner Exactly. Note that in the context of analyzing complexity, when someone gives a Big-Oh bound, this is usually the strongest bound that they could find. Which might still not be a Big-Theta bound, but it is way better than the *just some upper bound* that is required to satisfy the formal definition. – ComicSansMS Aug 05 '16 at 12:03
  • Thanks and now i am able to understand the topic. – Garrick Aug 05 '16 at 12:58
  • @Willturner I frown a bit on the "2^n = O(3^n)" ... I think "O(2^n) = O(3^n)" would be more correct, if you are really after equivalence. – Ped7g Aug 05 '16 at 15:33
  • @Ped7g Well, to be really pedantic: "O(2^n) ⊂ O(3^n)". The Big-O notation describes sets of functions and the set O(2^n) is a proper subset of O(3^n). Writing 'a function equals a set of functions' is of course not exact. But since the set-nature of the Big-O is often not of concern, it is actually a common notation in complexity theory. – ComicSansMS Aug 05 '16 at 17:17
  • @Ped7g, no it cannot be equivalent . Bcoz, saying "O(2^n) = O(3^n)" comes under set theory and it means function set of both the big O are equal , but is is not the case actually . Say 2.7^n , it belongs to O(3^n) but not O(2^n) . Instead, O(2^n) set should be a proper subset of the set O(3^n) . – Garrick Aug 05 '16 at 19:01
0

if you try to make 2^n is greater than 3^n to test if it's omega(3^n) and it can't be true as it will be

nlog2 > logc1 + nlog3 ( false) because logc1 > 0 and nlog3 > nlog2 so it is big O of it

عبدالرحمن مجدي
  • 1