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)). The total time complexity of the program given above becomes:

O(nlog2(n))O(nlog_2(n))

Here’s another way to arrive at the same result. Let’s look at the inner loop once again.

The inner loop depends upon j, which is less than i, and is multiplied by 2 in each iteration. This means that the complexity of the inner loop is O(log2(i))O(log_2(\text{i})). But the value of i at each iteration of the outer loop is different. The total complexity of the inner loop in terms of n can be calculated as such:

n×log2(i)⇒∑i=1nlog2(i)n \times log_2(i) \Rightarrow\sum_{i=1}^{n} log_2 (i)

⇒log2( ...