Time & Space Complexity – IV

In this post, I am going to talk about the time complexity of one more type of algorithms. Once again, we do not need to discuss the space complexity as it is going to be the same as all the other for loops.

In the previous post, I had given a small introduction of logarithmic functions. If you are not sure about how logarithm works, I’d suggest you go back and have a look (click here to read the basics of logarithms). It is essential to understand logarithms for today’s algorithm.

So, let’s jump to the next algorithm.

// Algorithm 1
1.  Algorithm ForLoop (N)
2.  begin
3.    for (i = 1; i <= n; i = i * 2) {
4.      //stmt
5.    }
6.  end

In this example, we see that ‘i’ is incremented by a multiplying factor of 2. Which is to say, the value of ‘i’ will be multiplied by 2 in every iteration.

iteration      value of i
=========      ===========
    1               1
    2               1*2 = 2^1
    3               1*2*2 = 2^2
    4               1*2*2*2 = 2^3
    .
    .
   k + 1            1*2*2*2*.... = 2^k
Let's assume, the break condition is reached when the value of i is 2 to the power k.

Then, we can write
=> value of i >= n
=> 2^k = n        // approximate values, removed less than
Taking log on both sides,
k = log (2) n

That is, we need to multiply 2 by 2; k times to get n.

The same will be the case if in the for loop, i is assigned a value of n, and its value is halved in every iteration.

for (i = n; i >= 1; i = i/2)

One thing to note here is, we always take the ceiling (upper limit) while calculating the time complexity.

Let us consider the values of N to be 8 and 10.
So,
k = log (2) 8              k = log (2) 10
k = 3                      k = 3.2 (rough estimate)

Now, the number of iteration always start with the value of i is 1, as we see in the above example.

iteration          value of i (<8)   value of i (<10)
===========        ==============    ================
1                      1 (T)               1 (T)
2                      2 (T)               2 (T)
3                      4 (T)               4 (T)
4                      8 (F)               8 (T)
5                      --                 16 (F)

The value of k comes to 3.2 (estimated value) when the value of n is 10. Hence we can conclude that while rounding off, we need to consider the upper limit because we see that the code of the loop run for 4 iterations.

Summary

for (i = 1; i < n; i++)               O (n)
for (i = 1; i < n; i = i+2)           O (n)
for (i = n; i >= 1; i--)              O (n)
for (i = 1; i < n; i = i *2)          O (log n)
for (i = n; i >= 1; i = i/2)          O (log n)
for (i = 1; i < n; i = i * 3)         O (log (3) n)