Java – Run time for nested while loops do not reset

Run time for nested while loops do not reset… here is a solution to the problem.

Run time for nested while loops do not reset

Is the following code O(n^2) or O(n)?

int i=0, j=0;
while (i < n) {
  while (j < n) {
    j++;
  }
  i++;
}

Since the inner while loop only runs once from 0 to n, I guess this is equivalent to having two separate while loops, so the total run time is O(2n).

Solution

In this particular piece of code is O(n).
For example
If n=10
The inner loop for i=0 executes from j=0 to j=9 (10 times) and the for i = 1 to 9 inner loop executes 0 times, (because j(10) >n(10) never becomes true),
So total time = 10 times outside + 10 times inside = 20 = 2n
Therefore, the time complexity is O(n).

Related Problems and Solutions