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
$\begingroup$
$\endgroup$
3
-
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$– RaphaelCommented Aug 28, 2018 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$– RaphaelCommented Aug 28, 2018 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$– RaphaelCommented Aug 28, 2018 at 18:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
14
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
-
$\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$– BulatCommented Aug 28, 2018 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$– ScottKCommented Aug 28, 2018 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$– BulatCommented Aug 28, 2018 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$– ScottKCommented Aug 28, 2018 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$– RaphaelCommented Aug 28, 2018 at 18:37