Big O notation explanation nested while loop

Question

I was wondering what the big o notation is for the following (java)code:

while (n > 0) {
     while (n > 0){
        n-- ;
    }
 } 

If I use n = 10 it will do one iteration in the outer loop and 10 inside the inner loop.
So a total of 11 iterations right?
if I use n = 100 it will de one iteration in the outer loop and 100 inside the inner loop.
So a total of 101 iterations right?
But this is the point where I got stuck. Because I think the notation is O(n). Simply because I think the iteration are almost equal to n. But I don't know how to prove it?

I am not that much in math so a clear explanation would be appriciated

Answer 1

Informally speaking, for positive arguments, the outer loop takes exactly one iteration, as in the inner loop n is decreased to zero. The inner loop will take exactly n iterations, so the runtime complexity of the inner loop is O(n). In total, although the termination condition of the outer loop syntactically depends on n, it is in fact independent from n. The overall complexity can be seen as O(n+c) where c is a constant representing the execution of the outer loop. However, O(n+c) equals O(n).

What probably puzzles you is that in your terminology, you speak of a number of 101 iterations of a loop, where you in fact refer to two different loops.

Answer 2

It's O(n), because the outer loop runs one single time. When the inner loop finishes, then the condition for the outer loop is also false. Therefore the outer loop is not important to the O notation.