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

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

Explore how nested loops with geometric progression impact algorithm time complexity. Learn to analyze and calculate the Big O notation for such loops, especially those involving logarithmic outer loops and multiplicative inner loops, to better evaluate algorithm efficiency in your C# code.

We'll cover the following...

Solution

C#
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 is the number of iterations of the outer loop, the body of the inner loop runs a total of 1+2+4+8+⋯+2k1+2+4+8+\cdots+2^k times. This geometric series sums to 2k+1−12^{k+1}-1. The inner loop condition requires that in the last time the inner loop runs, it runs at most nn times. This requires 2k<n2^k < n ...