class NestedLoop {
public static void main(String[] args) {
int n = 13; // 1 step --> Note: n can be anything. This is just an example
int sum = 0; // 1 step
double pie = 3.14; // 1 step
int step = 0;
for (int var = 0; var < n; var = var + 3) { // n/3 steps
System.out.println("Pie: " + pie);
System.out.println("outer loop : " + ++step);
// n/3 steps
for (int j = 0; j < n; j = j + 2) { // (n/3 * n/2) steps
sum++; // (n/3 * n/2) steps
System.out.println("Sum = " + sum); // (n/3 * n/2) steps
}
}
}
}
The time complexity mentioned for this code is wrong :
The statement in course says , System.out.println("Pie: " + pie); will run n/3 times and var<n; will run n/3+1 times
But if you run above code , “outer loop:” gets printed 5 times when n = 13;
when it should have been printed 4 times according to course’s explaination
The correct number of times statement System.out.println("Pie: " + pie); will get printed is (n+2)/3 times
and var<n; will get checked (n+2)/3 + 1 times i.e; (n+5)/3 times
As 3k = (n-1) , k being number of times 3 will be added
and this quantity will be less than n
finally we will add 1 for var = 0 condition
which makes total iterations = (n-1)/3 +1 = (n+2)/3 =? no of times System.out.println("Pie: " + pie) is printed
