Time complexity of an algorithm with two nested loops

Question

Given this algorithm :

m = 1
while(a>m*b){
   m = m*2
}

while(a>=b){
   while(a>=m*b){
      a = a-m*b
   }
   m=m/2
}

My question : What is the time complexity of this algorithm ?

What I have done : I have to find the number of instructions. So I found out that, for the first while, there is m=log_2(a/b) iterations approximately. Now for the inner while of the second part of this algorithm, I found this pattern : a_i = a - i*m where i is the number of iterations. So there is a/bm iterations for the inner while.
But I don't know how to calculate the outer now because the condition depends on what the inner while have done to a.

meowgoesthedog · Accepted Answer · 2018-10-14T19:10:10.953

Let's begin by "normalizing" the function in the same way as in your previous question, noting that once again all changes in a and stopping conditions are proportional to b:

n = a/b

// 1)
m = 1
while(n>m){
   m = m*2
}

// 2)
while(n>=1){
   while(n>=m){
      n = n-m
   }
   m=m/2
}

Unfortunately, this is where the similarity ends...

Snippet 1)

Note that m can be written as an integer power of 2, since it doubles every loop:

i = 0
while (n > pow(2, i)) {
   i++
}
// m = pow(2, i)

From the stopping condition:

Snippet 2)

Here m decreases in the exact opposite way to 1), so it can again be written as a power of 2:

// using i from the end of 1)
while (n>=1) {
   k = pow(2, i)
   while (n >= k) {
      n = n - k
   }
   i--
}

The inner loop is simpler than the inner loop from your previous question, because m does not change inside it. It is easy to deduce the number of times c it executes, and the value of n at the end:

This is the exact definition of the Modulus operator % in the "C-family" of languages:

while (n>=1) {
   k = pow(2, i)
   n = n % k      // time complexity O(n / k) here instead of O(1)
   i--
}

Note that, because consecutive values of k only differ by a factor of 2, at no point will the value of n be greater than or equal to 2k; this means that the inner loop executes at most once per outer loop. Therefore the outer loop executes at most i times.

Both the first and second loops are O(log n), which means the total time complexity is O(log n) = O(log [a/b]).

Update: numerical tests in Javascript as before.

function T(n)
{
   let t = 0;

   let m = 1;
   while (n > m) {
      m *= 2; t++;
   }

   while (n >= 1) {
      while (n >= m) {
         n -= m; t++;
      }
      m/=2;
   }

   return t;
}

Plotting T(n) against log(n) shows a nice straight line:

Edit: a more thorough explanation of snippet 2).

At the end of snippet 1), the value of i = ceil(log2(n)) represents the number of significant bits in the binary representation of the integer ceil(n).

Computing the modulus of an integer with a positive power-of-2 2^i is equivalent to discarding all but the first i bits. For example:

n     = ...00011111111   (binary)
m     = ...00000100000   (= 2^5)
n % m = ...00000011111
                 -----   (5 least significant bits)

The operation of snippet 2) is therefore equivalent to removing the most significant bit of n, one at a time, until only zero is left. For example:

 outer loop no |           n
 ----------------------------
 1             | ...110101101
               |    ^
 2             | ...010101101
               |     ^
 3             | ...000101101
               |      ^
 4             | ...000001101
               |       ^ 
 :             | :
 :             | :
 i (=9)        | ...000000001
               |            ^
 ----------------------------
 final         |    000000000

When the current most significant bit (pointed to by ^) is:

0: the inner loop does not execute because the value of n is already smaller than k = 2^i (equal to the bit position value of ^).
1: the inner loop executes once because n is greater than k, but less than 2k (which corresponds the bit above the current position ^).

Hence the "worst" case occurs when all significant bits of n are 1, in which case the inner loop to always executes once.

Regardless, the outer loop executes ceil(log2(n)) times for any value of n.

Time complexity of an algorithm with two nested loops

1 Answers1