polynomial evaluation time complexity

Question

I was going through this link :
http://www.geeksforgeeks.org/horners-method-polynomial-evaluation/

Here it says that the time complexity using normal method is O(n^2).But I wonder how?Here is my analysis about this:

Suppose we have an equation like:2x^2 + x + 1
Here the for loop will be executed 3 times i.e.(order+1)times

    for(int i = order ; i>=0 ; i++){
         result = result + (mat[i] * coefficient^i);
    }

So according to this ,the time complexity should be O(n+1) i.e. O(n).Why does it say that its O(n^2)?I'm getting a little lost here.Even a hint would do.

Answer 1

Yes, you are right. The form you show is often called Horner's Method. It is linear in the sense that the number of elementary operations (additions, multiplications) is O(n), where n is the highest coefficient.

---

Incidentally, your code above seems to contain a mistake. It probably should be

for(int i = order ; i>=0 ; i--){

(the original is an infinited loop). Otherwise, it can be considered an implementation of Horner.