Suppose I have a value k whose value is $\log_2n$ and sum of geometric series $1+2+4+8+...+2^k$ is $2^{k + 1} -1$ . Now I am calculating the complexity of a simple nested loop program and the above computation is of the inner loop. The program is below for reference.
class NestedLoop {
public static void main(String[] args) {
int n = 10; // O(time complexity of the called function)
int sum = 0; //O(1)
double pie = 3.14; //O(1)
int var = 1;
while(var < n) {
System.out.println("Pie: " + pie);
for (int j = 0; j < var; j++) {
sum++;
}
var *= 2;
} //end of while loop
System.out.println("Sum: " + sum); //O(1)
} //end of main
} //end of class
Now the inner loop condition requires that in the last time the inner loop runs, it runs at most n times. This requires $2^k < n$ or $k < \log_2n$ . This means that the geometric series sum to $2^{\lfloor \log_2n \rfloor + 1} -1$ or $2^{\lceil \log_2n \rceil} -1$. In other words Thus, the number of iterations of the inner loop body is at least $n - 1$ and at most $2n - 3$ .
I am confused about the above conclusion. Can some one explain me in a verbose way of reaching the above statement of least and most terations of inner loop.
What you have done seems correct to me. Suppose $n$ is $k^{th}$ power of 2. Then, the outer loop runs $k$ times, which implies, inner loop runs $1+2+4+...+2^{k-1} = 2^{k}-1$ times.
Suppose n is $ 2^k + 1 $, the outer loop runs $k + 1$ times, hence the inner loop runs $2^{k+1}-1$ times. Now we can easily see that $\forall$ n $\in [2^k+1, 2^{k+1}]$, the number of times inner loop is executed is actually the same. Hence,
No of Times Inner loop executed(n) = $2^{k+1}-1$, where n $\in [2^k+1, 2^{k+1}]$, for some k $\in \mathbb{W}$
if $n = 2^{k+1}$, then No of Times Inner loop executed(n) = $2^{k+1}-1 = n-1$
if $n = 2^{k} + \alpha$, then No of Times Inner loop executed(n) = $2^{k+1}-1 = 2*(n-\alpha) - 1 = 2n - 2\alpha-1 \le 2n-3$ (least value of $\alpha$ is 1)