algorithm : what's the relationship between k and n? -

algorithm : what's the relationship between k and n? -

to calculate value of a^n:

method1:

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

if improved using method2:

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

how can deduce relationship between k , n? , why? thanks!

in first case result = a^n, in sec case result = a^(2^k), 2^k = n , k = logn. of course of study right n powers of 2.

algorithm