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

Solution Review: Nested Loop with Multiplication (Pro)

Explore how to analyze a nested loop structure where the inner loop increments logarithmically due to multiplication. Learn to calculate the total number of executions and derive the Big O time complexity to better understand algorithm efficiency in coding interviews.

We'll cover the following...

Solution

C#
namespace Chapter_1
{
    class Challenge_7
    {
        static void Main(string[] args)
        {
            int n = 10;    // O(1)
            int sum = 0;   // O(1)
            int j = 1;     // O(1)
            float pie = 3.14f; // O(1)
            for (int i = 0; i < n; i++) // O(n)
            {
                Console.WriteLine(pie); // O(n)
                while (j < i) // O(log2(n))
                {
                    sum += 1; // O(log2(n))
                    j *= 2;   // O(log2(n))
                }
            }
            Console.WriteLine(sum); // O(1)
            
        }
    }
}

The outer loop in the main function has “n” iterations as it iterates on i from 0 to n-1. If the condition j < i is true, the inner loop is entered. However, j is doubled immediately. Note that j is not reset to 1 in the code, since the j is immediately doubled. Therefore, the inner while loop will run O ...