Data Structures for Coding Interviews in C#/

...

/

Solution Review: Nested Loop with Multiplication (Basic)

Solution Review: Nested Loop with Multiplication (Basic)

This review provides a detailed analysis of how to solve the “Nested Loop with Multiplication” problem.

We'll cover the following...

Solution #

The code for this challenge is reproduced below:

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

Time complexity

The outer loop in this problem runs log3(n)log_3(n) times since counter will first be equal to 11, then 33, then 6, then 99, and ⋯\cdots until it is 3k3^k such that 3k<n3^k < n. In the inner loop, int j=1; runs log3(n)log_3(n) times. j<n gets executed log3(n)×(n2+1)log_3(n)\times(\frac{n}{2}+1) times, and j+=2 executed log3(n)×n2log_3(n)\times\frac{n}{2} times. The sum+=1; line also runs a total of log3(n)×n2log_3(n)\times\frac{n}{2} ...