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?

I thought I did it wrong too, I got a different answer too


Course: Data Structures for Coding Interviews in JavaScript - Learn Interactively
Lesson: Solution Review: Big (O) of Nested Loop with Multiplication - Data Structures for Coding Interviews in JavaScript

Hello,
sorry to disturb you.
My understanding is that if we want to calculate the number of repetitions when we have a series like
{1, 3, 5, 7, …} and we want to calculate the sum up to a given number we need to do
[(last - first) / the incremenet] + 1
I looked at this course as a reference
I think the author on Educative did not mention the +1 at the end because it is a constant and therefore It can be dropped when thinking of asymptotic functions.
However since he is trying to calculate exactly each part of the algorithm, I think it should be mentioned.
Hence in the example 10 - 0 = 10; 10/3 = 3; 3 + 1 = 4
Let me know if I am thinking incorrectly. I would like to have this clear in my mind without misunderstandings.
For the second loop we have 10 - 0 = 10; 10/2 = 5; 5 + 1 = 6;
6 x 4 = 24

Now, if we change the code and make it like var <=n and j<=n


We achieve exactly 24

If we use the strictly < for both loops we get 20 iterations in total of the inner loop.
9/3 + 1 = 3 +1 = 4
9/2 + 1 = 4 + 1 = 5
4 x 5 = 20