educative.io

Educative

Wrong Calculation of Running Time Complexity

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

​​

1 Like

I thought I was stuck Because I could not wrap my head around why the outer loop was meant to execute n/3 times.
For instance, take n=1
n/3 = 1/3 → and for java it is 0.
But in reality, if n=1, the loop executes once.

Agree with you, correct formula for amount if executions for the Outer loop is (n+2)/3.

Are these courses moderated?