2^n=O(3^n) : This is true or it is false if n>=0 or if n>=1 since 2^n may or not be element of O(3^n) I need a hint to figure the problem

  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Aug 28 '18 at 18:34
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Aug 28 '18 at 18:34
  • $\begingroup$ Note that as soon as O is involved, n tends towards infinity (in this context). So those lower bounds on n are irrelevant. $\endgroup$ – Raphael Aug 28 '18 at 18:35

It is a common misconception that O(g(N)) notation represents a function. It actually represents a set of functions whose asymptotic complexity is bounded by the function g(N) as N approaches infinity. In your example, g(N) = 3^N.

So to ask is 2^n = O(3^n) is mixing apples and oranges, or in this case you are comparing a function with a set of functions. We often write it this way, but it is understood that we are talking about membership in a set of functions, not equality.

The more correct way to state this is:

Is function 2^n contained in the set of functions represented by O(3^n)?

With the question phrased this way, the exact values of n do not enter into it because now you are asking if the function 2^n is a member of the set O(3^n).

The short answer is: yes it is.

But to understand why, you need to understand the formal definition of big-O notation which is:

   f(x) is contained in O(g(x)) 

if and only if for all sufficiently large values of x, the absolute value of f(x) is at most a positive constant multiple of g(x). That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that

|f(x)| <= Mg(x) for all x >= x0 

So for 2^n and O(3^n), we can set M to 1 and x0 to 1, and we get:

|2^n| <= 3^n for all n >= 1

With n=1, we have 2 <= 3, which is true. With n=2, we have 4 <= 9, which is also true, and informally we can see that 3^n grows faster than 2^n, so we know this relationship holds for all n > 2 as well, and thus:

2^n is contained in O(3^n)

For a more complete description of big-o notation, refer to this excellent post https://cs.stackexchange.com/a/23594/87624 or for something specific to BigO notation, read the Wikipedia article on big-o notation

| cite | improve this answer | |
  • $\begingroup$ The important point is that, AFAIK, in pure CS, O() considered as upper limit, while in practical programming it's considered as exact class so f.e. f(n)=n isn't in O(n^2) class (AFAIR I learned that from the popular "Cracking the Programming Interview" book and it corresponds to my own experience. $\endgroup$ – Bulat Aug 28 '18 at 7:27
  • $\begingroup$ @Bulat f(n)=n IS in O(n^2). O() is not the upper limit, it is an asymptotic bound in the limit of n, to within a constant multiple. So for example, f(2*n^2) is also in O(n^2), and is f(2*n^2 + 1000000), because in both cases as n gets large, there exists an n0 and an M, (in this case 2) such that these functions are bounded by Mg(x) which in this case is 2(n^2). $\endgroup$ – ScottK Aug 28 '18 at 13:35
  • 1
    $\begingroup$ It's like Pidgin English - people in industry (including me) so rarely need these things, that it's easier to occasionally say "algorithm A has lower bound of O(n)" rather than to remember the correct notation $\endgroup$ – Bulat Aug 28 '18 at 15:00
  • 1
    $\begingroup$ @Balut, Absolutely true and I agree. For industry, that short hand is perfectly awesome for a design discussion! The more formal notation and ideas would get in the way of a great discussion on design. $\endgroup$ – ScottK Aug 28 '18 at 15:21
  • 1
    $\begingroup$ @Bulat In practice, O shouldn't factor into a design (without detailed understanding) because it may provide many a red herring. $\endgroup$ – Raphael Aug 28 '18 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.