Data Structures for Coding Interviews in C#/

...

/

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

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

This review provides a detailed analysis of the time complexity of the "Nested Loop with Addition" problem!

We'll cover the following...

Solution

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

On line 11 in the outer loop, int i=0; runs once. i<n; gets executed n3+1\frac{n}{3}+1 times, and i+=3 executed n3\frac{n}{3} times. In the inner loop, int j=0; gets executed n3\frac{n}{3} times in total. j<n; executes n3×(n2+1)\frac{n}{3} \times (\frac{n}{2} +1) times, and j+=2 gets executed n3×n2\frac{n}{3} \times \frac{n}{2} times. See the following table for a detailed line-by-line analysis of the calculation of time complexity.

Statement
Number of Executions
int n = 10;
1
int sum = 0;
1
float pie = 3.14;
1
int i=0;
11
i<n;
...