0

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
6 Years
Discussion Span
Last Post by Rashakil Fol
0

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

0

> 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

0

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.

0

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

0

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.