1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Can you explain how you get to $O(m^3)$? Also, I'm still not sure where my approach is flawed. $\endgroup$
    – balderdash
    Sep 19, 2018 at 14:28
  • $\begingroup$ @balderdash Im sorry It should be $O(b^3)$ not $O(m^3)$. I'll edit my answer to include an example to make it clear. $\endgroup$ Sep 19, 2018 at 15:11
  • $\begingroup$ Your remarks are based on the assumption that $m \leq n$, right? $\endgroup$
    – balderdash
    Sep 20, 2018 at 7:03
  • $\begingroup$ @balderdash Yes it is valid $\forall m=o(n)$. $\endgroup$ Sep 20, 2018 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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