What would be the time complexity of this two nested loops

user_16943869 0
Viewed 275

given:

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

I'm 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

big-o algorithm
2 Answers

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)).

Bill_the_Lizard_12880

The total cost of the algorithm is O(n).

More specifically, the for loop has n iterations, and each iteration takes a constant amount of time. (By the way, after log n of these n iterations, i would have reached 0. For the remaining n - log n iterations, i continues to be equal to 0. The print statement is executed during each of these n iterations.) So, the total cost of the for loop is O(n). At the end of these n iterations, i is 0, and so the while loop exits after the first iteration.

user_78365590
Related