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?

up vote 1 down vote accepted

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

  • Can you explain how you get to $O(m^3)$? Also, I'm still not sure where my approach is flawed. – balderdash Sep 19 at 14:28
  • @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. – RandomPerfectHashFunction Sep 19 at 15:11
  • Your remarks are based on the assumption that $m \leq n$, right? – balderdash Sep 20 at 7:03
  • @balderdash Yes it is valid $\forall m=o(n)$. – RandomPerfectHashFunction Sep 20 at 14:12

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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