educative.io

Solution Review: Nested Loop with Multiplication (Advanced) - Data Structures for coding interviews in Java

Courses
, ,
#1 
for (int var = 0; var < n; var++) {    //O(n)
  int j = 1;  //O(n)
		System.out.println("Pie: " + pie); //O(n)
		while(j < var) { // O((n) * (log2 var))
    sum += 1; // O((n) * (log2 var))  
    j *= 2;  // O((n) * (log2 var))
  }
} /

The time complexity for an inner while loop is calculated as log2var, but as per the logic control never goes into while loop because j<var condition always fails. As j is incremented twice per run and var incremented by 1. Can somebody clarify whether we need to take into consideration the logic of the code or just calculate the time complexities?

#2

@KANITI_SARAT_KUMAR For every run of inner loop, j is reset to 1. The inner loop can also be written like this.
for (int var = 0; var < n; var++) { //O(n)
System.out.println("Pie: " + pie); //O(n)
for (int j = 1; j < var; j *= 2) {
sum += 1;
}
}
Hope this helps.