Skip to main content
3 of 6
rewrote a little, added links

Big O with multiple variables ($n,m$): Is $O((n+1)^m) = O(n^m)$?

In the big O notation with multiple variables ($n,m$), is $O(n+1)^m = O(n^m)$?


Details:

My intuition said yes, since adding a constant should neither have an effect in big O notation, even in a base. But since the exponent is also a variable and not a constant, I am not able to prove it. I tried for several definitions for Big O with multiple variables (https://en.wikipedia.org/wiki/Big_O_notation#Multiple_variables,http://math.stackexchange.com/q/353461/15523), but did not find suitable estimates.