Polynomial Complexity (Relative to the Size of the Input)

Question

I came across the following statement:

"Since b is smaller than n, the complexity $O((n + mb)^3)$ is polynomial."

I suppose it has something to do with the notion of polynomiality in terms of the input. All three variables are given as input. I am still not sure why it wouldn't be polynomial if $b$ was as big as $n$.

We could say $O(n + mn)^3)$ then which would be dominated by $O((mn)^3)$ for $m \geq 0$. It is even given, that $m \leq n$ which means that we can say $O(n^6)$ as worst case.

Now I would say this is certainly polynomial, because our solution is of the form $O(n^c)$ with $c \in \mathbb{R}$ which means that it is polynomial in the size of $n$.

What am I missing here?

Answer 1

The statement meant to say that "if b is asymptotically smaller than n" i.e. $b=o(n) \space or \space b=O(n)$.
If $b$ was asymptotically larger than $n$, i.e. $b=\omega (n) \space or \space b=\Omega(n)$, then the complexity would become, $O(b^3)$, i.e. not polynomial in $n$.
For example, lets consider two cases.

1. $b$ is asymptotically smaller than $n$, i.e. $b=O(n)$. $$O((n+mb)^3) = O(n^3 + 3n^2mb + 3nm^2b^2 + m^3b^3)$$ $$ = max(O(n^3),O(3n^2mb),O(3nm^2b^2),O(m^3b^3))$$ We know that $b=O(n) \implies bn=O(n^2),\space bn^2=O(n^3) \space and \space b^2n=O(n^3). $
   From this, we can conclude that, $m^3b^3=O(3nm^2b^2)$, $3nm^2b^2=O(3n^2mb)$, and $3n^2mb = O(n^3)$. $$\implies O((n+mb)^3)=O(n^3)$$

2. $b$ is asymptotically larger than $n$, i.e. $b=\Omega(n) \space or \space n=O(b)$. $$O((n+mb)^3) = O(n^3 + 3n^2mb + 3nm^2b^2 + m^3b^3)$$ $$ = max(O(n^3),O(3n^2mb),O(3nm^2b^2),O(m^3b^3))$$ We know that $n=O(b) \implies nb=O(b^2),\space nb^2=O(b^3) \space and \space n^2b=O(b^3). $
   From this, we can conclude that, $n^3=O(3n^2mb)$, $3n^2mb=O(3nm^2b^2)$, and $3nm^2b^2 = O(b^3)$. $$\implies O((n+mb)^3)=O(b^3)$$

In your approach, assuming $b$ to be numerically smaller than $n$ would lead to correct analysis. But what the statement means is that $b$ is asymptotically smaller than $n$. Like, $b=log(n) \space or \space b=\sqrt{n} \space or \space b=log(log(n))$