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$
13
  • 1
    $\begingroup$ What are $n,m$? Presumably you mean asymptotics in some sense. In what sense? $\endgroup$
    – GEdgar
    Commented Oct 17, 2015 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
    Commented Oct 17, 2015 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
    Commented Oct 17, 2015 at 21:41
  • $\begingroup$ @GEdgar, yes, $n$, $m$ are both variables, and I am considering the limit behavior towards infinity. $\endgroup$
    – DaveBall aka user750378
    Commented Oct 17, 2015 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
    Commented Oct 19, 2015 at 9:47

1 Answer 1

Reset to default
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$
4
  • $\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
    Commented Oct 17, 2015 at 21:53
  • 1
    $\begingroup$ @Dave Sorry but this very much answers the question (by the negative). $\endgroup$
    – Did
    Commented Oct 17, 2015 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
    Commented Oct 17, 2015 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
    Commented Oct 25, 2015 at 7:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .