Big-O of 2^(100n)?

[pandaEater]

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)

[abelLazm]

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)

[Rashakil Fol]

> 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.

[mrnutty]

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.

[geojia]

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.

[Rashakil Fol]

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.