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

Solution: Nested Loop with Multiplication (Pro)

Explore the time complexity analysis of a nested loop where the inner loop variable doubles each iteration. Learn how to calculate the worst-case running time and interpret the resulting O(n) complexity. This lesson helps you understand practical application of asymptotic analysis in coding challenges.

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) ...