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

Well it might not be so obvious but some primitive operations have different time complexity. Computer is very fast in computing the result of + operation, * - is slower, % - is even more slower. These operations are evaluated on hardware so they take constant number of processor ticks.

But ^ operation is not so simple. coefficient^i complexity is not O(1)/constant. Trivial way to calculate the result is to multiply the coefficient i number of times. This will be done in O(i) time. Another way is to use binary exponentiation method that gives faster O(log(i)) time.

Why does it say that its O(n^2)?

You have n members in polynomial, you spend O(n) time to calculate the result of the exponentiation operation for each of them. That is why it is O(n²).