CODEWITHSUNDEEP
c++algorithmmathbig-otime-complexity
user2809437
user2809437

Reputation: 492

How did this algorithm for computing a^n get rewritten to run in O(log n) time?

Suppose you want to compute an. A simple algorithm would multiply a, n times, as follows:

result = 1;
for(int i =1; i <= n; i++)
    result *= a;

The algorithm takes O(n) time. Without loss of generality, assume n=2^k

You can improve the algorithm using the following scheme:

 result = a;
 for (int i = 1; i <= k; i++)
     result = result * result;

The algorithm takes O(log n) time. For an arbitrary n, you can revise the algorithm and prove that the complexity is still O(logn)

So confused, so how is n=2k, and why is k only shown in the second example? Don't understand how this transformed into a O(logn) time complexity...

Upvotes: 3

Views: 1023

Answers (1)

templatetypedef
templatetypedef

Reputation: 373002

The second algorithm doesn't work in the general case; it only works if there is some k such that you can write n = 2k. If there is a k where you can do this, then by taking the logs of both sides of the equality you get that log2 n = k. Therefore:

  • The loop, which counts up to k, runs O(log n) times.
  • Therefore, the loop runs in time O(log n).

If you want to get rid of the mysterious k, you could write

int result = a;
for (int i = 0; i < log2(n); i++) {
    result = result * result;
}

This more clearly runs in O(log n) time, since the loop runs log2 n times and does O(1) work on each iteration.

I don't think it's fair to say "without loss of generality" that n is a perfect power of two, since not all numbers are! The above code will only work if n is a power of two. You can generalize it to non-powers-of-two by using the repeated squaring algorithm, which has O(log n) complexity but works for any power.

Hope this helps!

Upvotes: 9

Related Questions