1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What are $n,m$? Presumably you mean asymptotics in some sense. In what sense? $\endgroup$ – GEdgar Oct 17 '15 at 20:18
  • 1
    $\begingroup$ $O$ is usually defined only for a single-variable functions. Do you intend one of $n,m$ to be fixed? If so, which one? $\endgroup$ – Wojowu Oct 17 '15 at 20:30
  • $\begingroup$ Big O can be defined for multiple variables. This is quite relevant for complexity considerations, since often the complexity depends on multiple parameters. $\endgroup$ – DaveBall aka user750378 Oct 17 '15 at 21:41
  • $\begingroup$ @GEdgar, yes, $n$, $m$ are both variables, and I am considering the limit behavior towards infinity. $\endgroup$ – DaveBall aka user750378 Oct 17 '15 at 21:44
  • 3
    $\begingroup$ 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? $\endgroup$ – Did Oct 19 '15 at 9:47
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – DaveBall aka user750378 Oct 17 '15 at 21:53
  • 1
    $\begingroup$ @Dave Sorry but this very much answers the question (by the negative). $\endgroup$ – Did Oct 17 '15 at 22:20
  • $\begingroup$ 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? $\endgroup$ – DaveBall aka user750378 Oct 17 '15 at 22:40
  • 2
    $\begingroup$ @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. $\endgroup$ – Antonio Vargas Oct 25 '15 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.