Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C#

Solution: Big O of a Nested Loop with Multiplication

Explore how to analyze the time complexity of nested loops with multiplicative growth in this lesson. Learn to apply Big O notation to loops where the outer loop runs logarithmically and the inner loop grows exponentially, enabling precise complexity evaluation in coding interviews.

We'll cover the following...

Solution #

C# 9.0
int n = 10; // Can be anything
int sum = 0;
double pie = 3.14;
int i = 1;
while (i < n)
{
    System.Console.WriteLine(pie);
    for (int j = 0; j < i; j++)
    {
        sum += 1;
    }
    i *= 2;
}
System.Console.WriteLine(sum);

Explanation

The answer is O(n)O(n). Have a look at the slides below for an in-depth explanation of the answer.

Note: In the slides below, “RTC” is an abbreviation of running time complexity.

canvasAnimation-image
1 / 16

Time complexity

The above slides give a detailed, step-by-step analysis of the code. Here, we provide a more summarized version.

The outer loop here runs log⁡(n)\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 22. So, if kk is the number of iterations of the outer loop, the body of the inner loop runs a total of 1+2+4+8+⋯+2k1+2+4+8+\cdots+2^k times. This geometric series sums to 2k+1−12^{k+1}-1. The inner loop condition requires that in the last time the inner loop runs, it runs at most nn ...