Data Structures for Coding Interviews in C#/

...

/

Solution Review: Nested Loop with Multiplication (Advanced)

Solution Review: Nested Loop with Multiplication (Advanced)

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

We'll cover the following...

Solution #

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

In the main function, the outer loop is O(n)O(n) as it iterates n times. The inner while loop iterates i times, which is always less than n and the inner loop counter variable is doubled each time. Therefore, you can say that it is O(log2(n))O(log_2(n)) ...