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?
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
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.
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.
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)