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?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top