Time complexity of nested loops

Question

for(int i = 1; i < n; i = i ∗ 2){
     for(int j = 0; j < n; j++){
         if(i == j){
            for(int k = 0; k < n; k++){
               // Do something elementary
            }
         }else{
            // Do another elementary thing
         }
     }
 }

I am doing some exercise, and can someone please help me to figure out the Θ of the above algorithm? I understand that if it was just the two outer nested loops, the time complexity should be Θ(nlogn). But I don't know how to treat the if-else statement. Many thanks in advance!

Answer 1

You execute the outer loop log(n) times, because you double the value for i every time

Then you execute the inner loop n times, and the last inner loop inf the if statement you execute once (if i == j holds) n times, this the whole inner loop needs n + n steps each time.

This gives you an upper bound of O(2n log(n)) and since constants do not change the asymptotic complexity the runtime is bounded by O(n log(n))

for(int i = 1; i < n; i = i ∗ 2){                    ----------
 for(int j = 0; j < n; j++){            ----------             |
     if(i == j){                                  |            |
        for(int k = 0; k < n; k++){     ----      |            |
           // Do something elementary       | (n  | + n )      | * log(n)
        }                               ----      |            |
     }else{                                       |            |
        // Do another elementary thing            |            |
     }                                  ----------             |
 }                                                             |
}                                                              |
                                                   ------------

Note that the most inner loop is executed only once per second most inner loop (!) and since the second most inner loop gets executed log n times (with having n steps) we have to add the n times for the most inner loop to the runtime of the second most inner loop and then multiply it with the overall time the seondmost inner loop is executed