It is possible for an algorithm to have a negative coefficient in its time complexity, but in general, 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 complexity O(x^4) as follows:
for some suitable choice of x0 and and for all x> x0. To prove this, let x0 = 1 and M = 13. Then for all x> x0:
So
That is, even if negative coefficients are present in the original equation, some positive overall temporal complexity based on the term with the highest power order is still preserved.
What about the lower bounds? By definition, we can find the lower bound of any function using the following definition : since n goes to infinity, for some constant k and some n0 we have the following for all n>n0 :
Suppose the above function f (x) is also Omega (x ^ 4). It means that:
6x ^ 4 - 2x ^ 3 + 5> = kx ^ 4
Solution 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 is true, 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 found such a tight border that f(x) is Theta (x ^ 4).
Why does this work, although the coefficient was negative? For both Big O and Big Omega, we are looking for a boundary so that after some point one function dominates another. That is , as these graphs show :
(source: Alistair.Rendell at cs.anu.edu.au )
- Big O
(source: Alistair.Rendell at cs.anu.edu.au )
- Big Omega
Thinking of our original function f (x), 6x^4 grows faster than 2x^4 (our function kg (x)). After some time, the term 6x^4 will outstrip the growth of 2x^4 so that it will always be greater than 2x^4 . Graphically, two functions look like this:
Despite the negative coefficient, it is clear that kg(x) is the lower boundary of f(x) .
Now, is this always true for any polynomial function with any negative coefficient - that the function f(x) with any coefficients will be connected by its polynomials of the highest degree? Not. If the term with the highest degree has a negative coefficient, then the boundaries do not quite coincide. 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 (since c by definition a positive constant). However, if we try to do the same for the lower bound:
-2x ^ 2> = cx ^ 2 -2 <= c
Then we cannot find the correct c , because again c must be non-negative.