The time complexity with conditional statements

Question

How does one calculate the time complexity with conditional statements

i=1
while i<=n
    j=1
    while i<=n
       if i==j
          k=1
          while k<=j
             k+=1
             print("hello")
       else
          print(""world)
       j*=2
   i*=2

The time complexity is θ(nlgn) or θ(lgn*lgn)?

Good to refer: https://stackoverflow.com/questions/37965609/time-complexity-with-conditional-statements — Mebin Joe, Apr 11 '19 at 10:17
This algorithm does not end when *n* is greater than 0. Maybe it was intended to have `j<=n` as end-condition of the inner `while`? — trincot, Apr 11 '19 at 11:15
Several of the tutorials on determining complexity deal with conditionals. In short, you need to consider the average or worst-case condition (depending on which "complexity" you need) for each situation. — Prune, Apr 11 '19 at 17:19

trincot · Accepted Answer · 2019-04-11T13:24:18.590

Assuming that the second while loop should read while j<=n, the time complexity is:

O(n)

And the determining factor is exactly that loop on k.

We have:

i=1
while i<=n
    j=1
    while j<=n
        if i==j
            k=1
            while k<=j
                k+=1
                print("hello")
        else
            print("world")
        j*=2
    i*=2

The case i==j happens exactly once per iteration of the outer loop (where i changes), and could be made independent of the value of j, and taken out of the loop on j:

i=1
while i<=n
    j=1
    while j<=n
        if i!=j
            print("world")
        j*=2
    k=1
    while k<=i
        k+=1
        print("hello")
    i*=2

This changes the order of the print outputs, but that is irrelevant for determining the time complexity. We can even split that further:

i=1
while i<=n
    j=1
    while j<=n
        if i!=j
            print("world")
        j*=2
    i*=2

i=1
while i<=n
    k=1
    while k<=i
        print("hello")
        k+=1
    i*=2

So now for one iteration of the first outer loop, its inner while-loop iterates logn times. Each iteration of that inner loop takes constant time. In one case (when i equals j), there is a constant amount of time less work, so we have a time complexity of O(logn)-O(1) = O(logn) for this while loop.

That gives the first outer loop a time complexity of:

O(logn) * O(logn) = O((logn)²)

For one iteration of the second outer loop, its inner while-loop iterates i times, so we get a total number of iterations (when n is a power of 2) of 1 + 2 + 4 + 8 + ... + n, which is a binary expansion -- equal to 2(2^logn)-1 = 2n-1, giving a time complexity of:

O(2n-1) = O(n)

For the overall time complexity, we take the sum, i.e.

O((logn)²) + O(n) = O(n).

Illustration

To illustrate this time complexity, have a look at this implementation, where n is increased in each execution, and the units of work are counted and returned. The ratio between n and the amount of work approaches a constant:

function work(n)  {
    var units = 0;
    var i=1
    while (i<=n) {
        var j=1
        while (j<=n) {
            if (i==j) {
                var k=1
                while (k<=j) {
                    k+=1
                    //print("hello")
                    units++;
                }
            } else {
                //print("world")
                units++;
            }
            j*=2
        }
        i*=2
    }
    return units;
}

// Demo
setTimeout(function loop(n=1) {
    var units = work(n);
    console.log(`n=${n}, work=${units}, ratio=${units/n}`);
    if (n < 100000000) setTimeout(loop.bind(null, n*2));
});

This is only an illustration, and does not count as proof.

The time complexity with conditional statements

1 Answers1

Illustration