Time complexity of powering a number

Question

Learning from MIT Opencourseware's algorithms course, a professor talks about powering a number and its time complexity.

x^n simply is computed as x*x*x...... n times (imagine a simple for loop with a multiplication being performed inside it)

He states that the time complexity of this approach is theta(n).

Here is my analysis:

Let the N(x) be a function that gives the number of digits in x. Then, complexity of :

x*1 = N(x)

x*x = N(x)*N(x)

x*x*x = N(x^2) * N(X)

x*x*x*x = N(x^3) * N(x)

and so on......

To sum up, T(x^n) = N(x) + N(x)*N(x) + N(x^2)*N(x) + N(x^3)*N(x) + ........... N(x^(n-1))*N(x)

T(x^n) = N(x)[1 + N(x) + N(x^2) + N(x^3) + ....... N(x^n-1)]

However, i can't solve any further. How does it yield theta(n) ultimately?

Answer 1

Think of it like this.

If you conisder multiplication between two numbers to be an operation that takes unit time. Then the complexity of a 2 number multiplication is done in theta(1) time. Now, in a for loop which runs for n-1 times for n numbers. You apply this operation n-1 times. So the theta(1) cost operation happens N-1 times which makes the overall cost of the operation theta(n-1) which in asymptotic terms is theta(n)

The multiplication happens like this

• x=x
• x^2 = x*x
• x^3 = (x^2)*x
• x^4 = (x^3)*x
• ................
• .................
• .................
• x^(n-1) =(x^(n-2))*x
• x^n = (x^(n-1))*x

It's theta(1) for each step as you can use the result of a previous step to calculate the overall product. For example, when you caculate x^2. You can store the value of x^2 and use it while calculating x^3. Similarly when you calculate x^4 you can use the stored value of x^3.

Now all the individual operations take theta(1) time. If you do it n times, the total time is theta(n). Now for calculating the complexity of x^n.

• for x^2, T(2) = theta(1)
  This is the base case for our induction.
  
• Let us assume for x^k, T(k) = theta(k) to be true
  
• x^(k+1) = (x^k)*x, T(k+1)= theta(k)+theta(1)

Hence, for x^n, time complexity is T(n) = theta(N)

and if you want to sum up the complexity. You are summing it up wrong.

We know that T(2) = theta(1), time complexity of multiplying two numbers.

• T(n) = T(n-1)+T(2) (time complexity of multiplying two numbers and time complexity of multiplying (n-1) numbers)
• T(n) = T(n-2)+T(2)+T(2)
• T(n) = T(n-3)+T(2)+T(2)+T(2)
• ...................
• ...................
• T(n) = T(3) + (n-3)*T(2)
• T(n) = T(2) + (n-2)*T(2)
• T(n) = (n-1)*T(2)
• T(n) = (n-1)*theta(1)
• T(n) = theta(n)

As you know C an example of how you will write a power(naive) function.

 int power(int x,int n)
 {
     int powerVal=1;
     for(int i=1;i<=n;++i)
     {
          powerVal=powerVal*x;
     }
     return powerVal;
 }

Now, as you can see each time multiplication of two integer takes place and that takes only theta(1) time. You run this loop n times. so total complexity is theta(n)

Answer 2

You're waaaaaay off-track.

Multiplication is a single operation.

You are applying this operation n times.

Therefore, O(1*n), which is O(n).

Done.

Answer 3

If you're looking for a best algorithm to compute power of a given number, it's not the best solution. Indeed, power of a number is not computed as you said, this method gives a complexity o(n) because you're applying the same operation n times X*X*...*X. The algorithm below gives a complexity o(log n):

pow(x,n)
{
  R=1; X=x; N=n;
   while (N > 0)
   {
      if N mod 2=1  R= R*X
      N= N div 2
      X= X · X
   }
   return R
}