Negative Coefficients in Polynomial time Complexit

Question

Assuming some algorithm has a polynomial time complexity T(n), is it possible for any of the terms to have a negative coefficient? Intuitively, the answer seems like an obvious "No" since there is no part of any algorithm that reduces the existing amount of time taken by previous steps but I want to be certain.

Answer 1

It is possible for an algorithm to have a negative coefficient in its time complexity, but overall the algorithm will have some positive time complexity. As an example from Wikipedia, take the function f(x)=6x^4-2x^3+5. They solve for the complexity of O(x^4) as follows:

for some suitable choice of x0 and M and for all x > x0. To prove this, let x0 = 1 and M = 13. Then, for all x > x0:

So,

That is, even if there are negative coefficients in the original equation, there is still some positive overall time complexity based on the term with the highest order of power.

---

What about for lower bounds? By definition, we can find the lower bound of any function by using the following definition: As n goes to infinity, then for some constant k and some n0 we have that the following holds for all n>n0:

Let's guess that the above function f(x) is also Omega(x^4). This means that:

6x^4 - 2x^3 + 5 >= kx^4

Solving for k:

k <= (6x^4 - 2x^3 + 5)/(x^4)

k <= 6 - 2x^-1 + 5x^-4

The term (2/x) approaches 0, as does (5/x^4) so we can choose k=2 for some large x0=30. To show that this holds, we show that:

6x^4 - 2x^3 + 5 >= 2x^4 where x > 30

4x^4 - 2x^3 + 5 >= 0

Which holds. So f(x) is Omega(x^4), and we can also conclude that we have found a tight bound such that f(x) is Theta(x^4).

Why does this work, even though the coefficient was negative? For both Big O and Big Omega notation, we are looking for a bound such that after some point one function dominates another. That is, as these graphs illustrate:

http://cs.anu.edu.au/~Alistair.Rendell/Teaching/apac_comp3600/module1/images/Introduction_BigOGraph.png -- Big O

http://cs.anu.edu.au/~Alistair.Rendell/Teaching/apac_comp3600/module1/images/Introduction_BigOmegaGraph.png -- Big Omega

Thinking about our original f(x), 6x^4grows faster than 2x^4 (our kg(x) function). After some point, the 6x^4 term will outstrip the growth of 2x^4 in such a way that it is always greater than 2x^4. Graphically, the two functions look like this:

http://www3.wolframalpha.com/Calculate/MSP/MSP8991a0763a90cg9c64500002i49d6b33c5684hg?MSPStoreType=image/gif&s=47&w=319&h=132&cdf=RangeControl

Despite the negative coefficient, clearly kg(x) is a lower bound of f(x).

---

Now, is this always true for any polynomial function with any negative coefficient--that a function f(x) with any coefficients will be bound by its highest degree polynomials? No. If the term with the highest degree has the negative coefficient, then the bounds aren't quite the same. Take f(x) = -2x^2. We can show that f(x) = O(x^2):

-2x^2 <= cx^2 -2 <= c

Which can be satisfied by any c>0 (as c is by definition a positive constant). However, if we try to do the same for lower bound:

-2x^2 >= cx^2 -2 <= c

Then we can't find the right c because again c must be non-negative.

Answer 2

When talking about polynomial complexity, only the coefficient with the highest degree counts.

But I think you can have T(n) = n*n - n = n*(n-1). The n-1 would represent something you don't do on the first or last iteration.

Anyway, the complexity would still be n*n.