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

Solution: Nested Loop with Multiplication (Advanced)

Understand how to evaluate the time complexity of nested loops where the inner loop multiplies its counter. Explore practical step-by-step asymptotic analysis to derive the O(n log n) complexity using logarithmic properties and factorial simplification.

We'll cover the following...

Solution

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

Explanation

In the main function, the outer loop is O(n)O(n) ...