educative.io

A Program With Nested for Loops

Courses
,
#1

class NestedLoop {
public static void main(String[] args) {
int n = 5; // 1 step
int m = 7; // 1 step
int sum = 0; // 1 step
for (int i = 0; i < n; i++) { // n steps
for (int j = 0; j < m; j++) { // nm steps
sum++; // nm steps
}
}
System.out.println("Sum: " + sum); // 1 step
}
}

TIme
TIme1156×650 58.3 KB

how it is came 1+1+1+6n+4+n(6m+4)+3nm+2… (6n+4)…

Course: Data Structures for Coding Interviews in Java - Learn Interactively
Lesson: Example: Time Complexity of an Algorithm With Nested Loops

#2

Hello,

I hope you’re doing fine. The breakdown is well explained in the slides.
Let’s go through this once again:

  • It is 4 till the first intialization in the outer for loop.
  • In the condition of the outter loop it’s i<n, this condition will account for 3(n+1) primitive operations.
  • Intialization in the inner for loop will take 1 unit of time, but it’s inside a for loop. It’ll be n for this step.
  • Just like we did in second step, it will be 3(m+1) for inner loop, but since it’s inside a loop, it’ll be n x 3(m+1).
  • sum++ is three step process, so it is 3m, but since it’s inside a nested loop, it’ll be n x 3m.
  • incrementing j is n x 3m
  • incrementing i is 3n
  • In the end, print statement accounts for 2 primitive operations.

Let’s add these:

Total = 4 + 3(n+1) + n + n x 3(m+1) + n x 3m + n x 3m + 3n + 2
= 4 + 3n + 3 + n + 3mn + 3n + 3mn + 3mn + 3n + 2
= 9 + 10n + 9mn