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)). Therefore, the total time complexity of the program given above becomes:

O(nlog⁡2(n))O(n \log_2(n))

Here’s another way to arrive at the same result. Let’s look at the inner loop once again.

The inner loop depends upon j, which is less than i and is multiplied by 2 in each iteration. This means that the complexity of the inner loop is O(log⁡2(i))O(\log_2(\text{i})). But, the value of i at each iteration of the outer loop is different. The total complexity of the inner loop in terms of n can be calculated as such:

n×log⁡2(i)⇒∑i=1nlog⁡2(i)n \times \log_2(i) \Rightarrow\sum_{i=1}^{n} \log_2 (i) ...