Algorithms for Coding Interviews in C#/

...

/

Solution: Nested Loop with Multiplication (Basic)

Solution: Nested Loop with Multiplication (Basic)

Review the solution to compute the Big O of an algorithm involving a nested loop with multiplication.

We'll cover the following...

Solution #

Press + to interact
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 ...