Search code examples
algorithmbig-o

What would be the time complexity of this two nested loops

given:

public void iterate(int n){
    int i =n;
    while (i > 0){
        for (int j = 0; j < n; j++) {
            System.out.println("*");
            i = i/2;
        }
    }
}

I might argue that the time complexity for this operation is linear because comparing i > 0 would be constant and the for loop inside would be linear. Therefore give a total of linear time.

But in my head, i still think the operation is quadratic.

Could anyone please give me a clearer explanation of the complexities on nested loops. Thanks

Solution

  • As written, the outer loop here isn't really doing anything, since i is decremented to 0 inside the inner loop. The while loop will only execute one time. The body of the for loop will execute n times, so the algorithm is O(n).

    If you moved i = i/2; to run after the for loop body, the while loop would execute log(n) times, so the algorithm would be O(n * log(n)).