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

Solution: Nested Loop with Multiplication (Basic)

Understand how to analyze a nested loop involving multiplication and calculate its time complexity using logarithmic functions. This lesson guides you through solving the problem step-by-step and deriving its Big O notation to assess performance during coding interviews.

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;
int i = 1;
while (i < n)
{
    System.Console.WriteLine(pie);
    for (int j = 1; j < n; j += 2)
    {
        sum += 1;
    }
    i *= 3;
}
System.Console.WriteLine(sum);

Explanation

The outer loop in this problem, i.e., everything under line 5, while (var < n) runs log⁡3(n)\log_3(n) times since var will first be equal to 11, then 33, then 9,⋯9,\cdots, until it is 3k3^k such that 3k≤n3^k \leq n. This means that the outer loop runs a total of log⁡3(n)\log_3(n) ...