What is the complexity of this function in terms of n?

Question

f(n):
   s = 1
   m = n
   while m >= 1:
       for j in 1,2,3, .., m:
           s = s + 1
       m = m / 2

My attempt

How many times does the statement s = s + 1 run? Well, let's try a number or two for n and see what we get.

n = 32
m = n = 32

m = 32 => inner for loop, loops 32 times
m = 16 => -.- 16 times
m =  8 => -.- 8 times
m =  4 => -.- 4 times
m =  2 => -.- 2 times
m =  1 => -.- 1 time

In total 16+8+4+2+1 = 31 times for n = 32

Doing the same for n = 8 gives 15 times
Doing the same for n = 4 gives 7 times
Doing the same for n = 64 gives 127 times

Notice how it always seemingly is 2 * n - 1, I believe this to be no coincidence because what we're really observing is that the total amount of times the statement gets executed is equal to the geometric sum sum of 2^k from k=0 to k=log(n) which has a closed form solution 2n + 1 given that we're using base 2 logarithm.

As such, my guess is that the complexity is O(n).

Is this correct?

Answer 1

Well what you just observed is true indeed. We can prove it mathematically as well.

1. Inner loop execution for first iteration -> n
2. Inner loop execution for second iteration -> n/2
3. Inner loop execution for third iteration -> n/(2^2) and so on....

Therfore total time is (n + (n/2) + (n/(2^2)) + ... + (n/(2^k))) where n/(2^k) should be equal to 1 which implies k = log(n). Taking n common from all terms will give us a GP And now using GP formulae in above series , total time will come out to be 1(1 - ((1/2)^k)) / (1 - 1/2). putting value of k = log(n), we will get total time as 2*(n-1).

Note -:

• This gives us time complexity of O(n).
• log is of base 2.