educative.io

Time complexity question

Courses
,
#1 
class NestedLoop {
	public static void main(String[] args) {
		int n = 10; // O(time complexity of the called function)
		int sum = 0; //O(?)
		double pie = 3.14; //O(?)
		int var = 1; //O(?)

		while(var < n) {
			System.out.println("Pie: " + pie); //O(?)
			for (int j = 0; j < var; j++) {
				sum++; //O(?)
			}
			var *= 2;  //O(?)
		} //end of while loop
		System.out.println("Sum: " + sum); //O(?)
	} //end of main
} //end of class

Why is j<var; executed 2n times?

#2

Hi @Mishal,

This is Fatimah Abdullah from Educative.

In the solution review lesson, we mentioned how the time complexity for the statements in the inner loop is calculated using the geometric series. The sum of the geometric series shows that statements inside the loop will be executed 2n - 1 times. Now, keeping that in mind, when we take a look at the comparison statement of the loop, which in this case is j < var, we know that it executes 1 more time than the statements inside the loop. This is because, when the condition returns false, then we do not execute the statements inside the loop. I hope this clears it up for you.

We hope Educative has inspired to further your learning, and please drop us a note if you have any other questions or concerns.

Best Regards,
Fatimah Abdullah | Developer Advocate
Educative