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

Solution: Nested Loop with Multiplication (Pro)

Learn to compute the Big O of an algorithm that involves nested loops, where the loop variables increase with each multiplication and addition.

We'll cover the following...

Solution #

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

Explanation

The outer loop in the main function has nn iterations because it iterates on the list generated from the for loop. If the condition j < var is true, the inner loop is entered. However, immediately, j is doubled. Note that j is not reset to 1 in the code. The inner while loop will run at most once for each iteration of the outer loop. Therefore, lines 6, 7 and 8 run O(n)O(n) ...