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

Question

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 (such as the one on the wikipedia page and the one on this math.SE precious question), but did not find suitable estimates.

• GEdgar: What are $n,m$? Presumably you mean asymptotics in some sense. In what sense?
• Wojowu: $O$ is usually defined only for a single-variable functions. Do you intend one of $n,m$ to be fixed? If so, which one?
• DaveBall aka user750378: Big O can be defined for multiple variables. This is quite relevant for complexity considerations, since often the complexity depends on multiple parameters.
• DaveBall aka user750378: @GEdgar, yes, $n,ドル $m$ are both variables, and I am considering the limit behavior towards infinity.
• Did: Reputation has nothing to do with the matter. The matter is that, reading your question in its present formulation, one fails to understand how it was not already fully answered by @GEdgar yesterday. One can even refine this answer, noting that $(n+1)^m$ is not in $O(n^m)$ when $n$ and $m$ go to infinity, unless $(n,m)$ is restricted to $m\leqslant Cn$ for some fixed $C$. To sum up, instead of focusing on the reopening of your question and repeating "please elaborate", why don't you study the answer you already received?

Answer 1

Note if $m=n^2,ドル then $$ \lim_{n \to \infty}\left(\frac{n^m}{(n+1)^m}\right) =\lim_{n \to \infty}\left(1+\frac{1}{n}\right)^{-n^2} = 0 $$

• DaveBall aka user750378: Thanks for the answer. This is an interesting fact, but does not answer my question, since $n$ and $m$ need not be dependent in the definition of big O for multiple variables (see e.g. wikipedia or the cited paper there).
• Did: @Dave Sorry but this very much answers the question (by the negative).
• DaveBall aka user750378: Hey, no need to apologize ;) Great if it answers my question. Now I only have to understand it. Could you please elaborate, Did or GEdgar?
• Antonio Vargas: @DaveBall, if it were true that $(n+1)^m = O(n^m)$ for $n,m > 0$ then there would be a constant $C > 0$ such that $(n+1)^m \leq Cn^m$ for all $n,m > 0,ドル and then $$\frac{n^m}{(n+1)^m} \geq \frac{1}{C} > 0, \qquad n,m > 0. \tag{$*$}$$ But GEdgar showed that the quantity $n^m/(n+1)^m$ can get arbitrarily close to 0ドル$ by choosing $n$ and $m$ in a certain way ($m=n^2$), and so $(*)$ cannot be true.