CODEWITHSUNDEEP
javaalgorithmtimetime-complexitybig-o
CosmicCat
CosmicCat

Reputation: 612

Misunderstanding small details w/ nested for-loop time complexity analysis... How to tell O(n) and O(n²) apart

For the algorithm below:

 int x = 0;
 for (int i = 0; i < n; i++)
     for (j = 0; j < n; j++) {
         if (j < i) j = j + n;
         else x = x + 1;
      }

So for this algorithm, my thought process goes like this:

The inner-loop performs n iterations for j when i=0. However, for every value of i=0,1..n-1, j will only perform one iteration because the if-statement will evaluate to true and end the inner-loop.

Here is my source of confusion:

Since the outer-loop will perform n iterations no matter what, and since the inner loop performs n iterations when i=0 (very first iteration), how come the big-Oh time complexity isn't O(n²) and is instead, O(n) if the loops are nested and both perform n iterations in the very first iteration?

Upvotes: 7

Views: 188

Answers (4)

Amit
Amit

Reputation: 2098

For every n outer iteration, there are n inner iterations. So you will do n*n=n^2 computations and hence the complexity is O(n^2). Does this make sense or it is more confusing?

Upvotes: -1

Oleksandr Pyrohov
Oleksandr Pyrohov

Reputation: 16216

You could just print the values of i and j from the inner loop:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.print(i + "" + j + " ");
        if (j < i) j = j + n;
        else x = x + 1;
    }
    System.out.println();
}

Output:

00 01 02 03 04 ..
10
20
30
40
..

Which represents only the first row and the first column of the matrix, thus the complexity is:

O(2n) => O(n).

Upvotes: 3

Michał Ziober
Michał Ziober

Reputation: 38655

You properly notice that only for i=0 inner loop will iterate n times. For i>0 inner loop runs once only. We can sum all these iterations: i0+i1+...+n-1, where i0=n, and for other indexes ix=1. So, sum of inner iterations will be n + n - 1 => 2n - 1. Which gives us: O(2n - 1) => O(2n) - O(1) => 2*O(n) - O(1) => O(n).

Upvotes: 1

RaminS
RaminS

Reputation: 2239

You have a line that says if (j < i) j = j + n; which essentially breaks out of the loop (when j < i), and since the inner loop starts at 0, this will trigger on the first iteration every time (except the first time), making it run in constant time.

You essentially only have one loop here. The code can be rewritten as

int x = 0;
for (int i = 0; i < n; i++) {
    x = x + 1;
}

which makes it clear why it is O(n).

Upvotes: 5

Related Questions