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

Solution: Nested Loop with Multiplication (Intermediate)

Explore how to analyze the time complexity of nested loops involving multiplication in C#. Understand the process of breaking down loop executions, applying Big O notation, and simplifying terms to determine overall algorithm efficiency.

We'll cover the following...

Solution

C# 9.0
int n = 10; // 'n' can be anything, this is just an example
int sum = 0;
double pie = 3.14;
for (int i = 1; i < n; i += 3)
{
    int j = 1;
    System.Console.WriteLine(pie);
    while (j < n)
    {
        sum += 1;
        j *= 3;
    }
}
System.Console.WriteLine(sum); // O(1)

Explanation

  • Outer loop: 1+4+7+10+⋯+n=n31+4+7+10+\cdots+n = \frac{n}{3}

  • Inner loop: 1+3+9+27+⋯+n=log⁡3n1+3+9+27+\cdots+n = \log_3 n ...