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

suppose want compute aⁿ. simple algorithm multiply a, n times, follows:

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

the algorithm takes o(n) time. without loss of generality, assume n=2^k

you can improve algorithm using following scheme:

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

the algorithm takes o(log n) time. arbitrary n, can revise algorithm , prove complexity still o(logn)

so confused, how n=2^k, , why k shown in second example? don't understand how transformed o(logn) time complexity...

the second algorithm doesn't work in general case; works if there k such can write n = 2^k. if there k can this, taking logs of both sides of equality log₂ n = k. therefore:

• the loop, counts k, runs o(log n) times.
• therefore, loop runs in time o(log n).

if want rid of mysterious k, write

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

this more runs in o(log n) time, since loop runs log₂ n times , o(1) work on each iteration.

i don't think it's fair "without loss of generality" n perfect power of two, since not numbers are! above code work if n power of two. can generalize non-powers-of-two using repeated squaring algorithm, has o(log n) complexity works power.

hope helps!