Big-O of 2^(100n)

I'm having some trouble figuring this one out. Basically I'm wondering if the constant multiple c is a multiple of n or a multiple of the whole function?

For example, if it were O(2^n) would you put the constant multiple next to n so it could be:
2^100n
or
do you have to put the constant multiple outside of the whole function so it would be:
100 * 2^n

Thanks for any help!

By the way this question is relating to a larger question:
You have functions f and g such that f(n) is O(g(n))
- 2^(f(n)) is O(2^(g(n))) : True or False?

I'm currently saying False because if f(n) = 100n and g(n) = n so f(n) is O(n)
then
no constant multiple C * 2^n will produce an upper bound for 2^(100n)

5
Contributors
5
Replies
6
Views
7 Years
Discussion Span
Last Post by Rashakil Fol

when we talk about constant multiplication with function we mean that the constant is to be multiplied with whole function and not with n only.
e.g. C*(8n^2 - 12n + 6) = (8C)n^2 + (-12C)n + (6C)

Edited by abelLazm: n/a

> I'm currently saying False because if f(n) = 100n and g(n) = n so f(n) is O(n)
then
no constant multiple C * 2^n will produce an upper bound for 2^(100n)

Why do you say no constant multiple C * 2^n will produce an upper bound for 2^(100n)?

So far you haven't done any work, you've merely rewritten the definition of O notation.

Edited by Rashakil Fol: n/a

Remember the keyword "constant" multiple. If you put the constant in the exponent, then there would be a exponential difference and not a constant difference.

In big-O notation constants doesn't matter. So is a program that makes 10 calls n times is O(n) such that if n=1 runtime =10
n=2 runtime = 10*(2)
...
n=infinity runtime =10(infinity) //here 10 doesn't matter in the sense of big-O notation
Also big-O notation assumes any constant multiplier so when you write O(n) it's assumed that it's actually O(k*n)

Back to your original question 2^(100*n) ->O(2^k*n) ==O(2^n). Note "2" is not a constant multipler, but base of a exponential. If you are trying to do (2*n)^(k*n) -> O(n^n) in this case "2" is a constant multiplier.

Hope this helps

Re firstPerson: a constant in the exponential does make an exponential difference but it's still a "constant exponential" difference compared to a exponential difference of n it's negligible.

Edited by geojia: 2nd look

geojia you're completely wrong, a function such as 2^(10*n) is not O(2^n). It is O(2^(10*n)) or O(1024^n). Which outgrows an O(2^n) function by (512^n). The ratio between the functions grows exponentially.

That's an exponential difference. It's not a "constant exponential" difference, which doesn't mean anything.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.