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

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

Explore the process of calculating the Big O time complexity for nested loops that include addition operations. This lesson helps you analyze each loop's execution count, combine them methodically, and simplify the result to identify the overall time complexity as O(n squared).

We'll cover the following...

Solution

C#
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;
...