Algorithms for Coding Interviews in C#/

...

/

Solution: Nested Loop with Multiplication (Advanced)

Solution: Nested Loop with Multiplication (Advanced)

Learn how to compute the Big O of an advanced and complex algorithm with nested loops involving multiplication.

We'll cover the following...

Solution #

Press + to interact
int n = 10; // 'n' can be anything
int sum = 0;
for (int i = 0; i < n; i++)
{
    int j = 1;
    while (j < i)
    {
        sum += 1;
        j *= 2;
    }
    System.Console.WriteLine(sum);
}

Explanation

In the main function, the outer loop is O(n)O(n) because it iterates over n. The inner while loop iterates over i, which is always less than n, and j is doubled each time. Therefore, we can say that it is O(log⁡2(n))O(\log_2(n)) ...