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

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

Explore how to analyze the time complexity of nested loops by examining each statement's execution frequency in C#. Learn to calculate running time and simplify to Big O notation, focusing on O(n squared) complexity.

We'll cover the following...

Solution

C#
namespace Chapter_1
{
    class Challenge2
    {
        static void Main(string[] args)
        {
            int n = 10;   
            int sum = 0;
            float pie = 3.14f;
            for (int i = n; i >= 1; i -= 3) // O(n/3)
            {
                Console.WriteLine(pie); // O(n/3)
                for (int j = n; j >= 0; j--)  // O((n/3)*(n+1))
                {
                    sum += 1;   // O((n/3)*(n+1))
                }
            }
            Console.WriteLine(sum);
            return;
        }
    }
}

On line 10 in the outer loop, int i=n; runs once. i>=1; gets executed n3+1\frac{n}{3}+1 times, and i-=3 executed n3\frac{n}{3} times. In the inner loop, int j=n; gets executed n3\frac{n}{3} times in total. j>=0; executes n3× (n+2)\frac{n}{3} \times \ (n+2) times, and j-- gets executed n3× (n+1)\frac{n}{3} \times \ (n+1) ...