Data Structures for Coding Interviews in C#/

...

/

Solution Review: Big (O) of Nested Loop with Multiplication

Solution Review: Big (O) of Nested Loop with Multiplication

This review provides a detailed analysis of how to solve the Big O of the "Nested Loop with Multiplication" challenge.

We'll cover the following...

Solution

Press + to interact
namespace Chapter_1
{
    class Challenge_3
    {
        static void Main(string[] args)
        {
            int n = 10; 
            int sum = 0;
            float pie = 3.14f;
            int counter = 1;
            while (counter < n) // O(log n)
            {
                Console.WriteLine(pie); // O(log n)
                for (int j = 0; j < counter; j++)// 8n - 12
                    sum += 1;// (4n - 6)
                counter *= 2;// O(log n)
            }
            Console.WriteLine(sum);
        }
    }
}

Time Complexity

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 2. So, if kk ...