Worst complexity of fast method

#1

why the worst complexity of the fast method is log n ?

#2

You are just iterating over the bits of the binary representation of power b.
Number of bits = log(n).
hence logn time.

#3

Can you please explain this in brief.

#4

7 is written as 111
if you want to take a^7 , we iterate over these 3 bits of 7. to
if you want to take a^32, we iterate over 100000 these 5 bits.
Hence log(32) = 5.

#5

thanks @Jun18APP0015

#6

Hit like if you have got it!
You may mark the thread as resolved now :smile:

1 Like