Solution: Big (O) of Nested Loop With Multiplication

Solution #

Time Complexity

The outer loop here runs $log(n)$ times. In the first iteration of the outer loop, the body of the inner loop runs once. In the second iteration, it runs twice, and so on. The number of executions of the body of the inner loop increases in powers of 2. So, if $k$ is the number of iterations of the outer loop, the body of the inner loop runs a total of $1+2+4+8+\cdots+2^k$ times. This geometric series sums to $2^{k+1}-1$. 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$ ...