GO Classes DPP | GATE DA | Python & DSA | Dependent Loops

Answer 1

The outer loop runs $n$ times.

The inner loop does not always run $n$ times. Its count depends on $i$.

$i = 0  \rightarrow$ inner loop runs $n - 1$ times
$i = 1  \rightarrow$ inner loop runs $n - 2$ times
$i = 2  \rightarrow$ inner loop runs $n - 3$ times
$...$
$i = n-1 \rightarrow$ inner loop runs $0$ times

Total work is:

$(n - 1) + (n - 2) + ... + 1 + 0$
$= n(n - 1)/2$
$= \mathrm{O(N^2)}$

Therefore, the Big-O efficiency is $\mathbf{O(N^2)}$.

Correct Option: D

Answer 2

def f1(n):
    ret = []
    for i in range(n):              # runs n times
        for j in range(i + 1, n):   # runs n-i-1 times
            ret.append(i + j)       # has cost O(1)
    return ret

So we end up with

$\sum_{i=0}^{n-1} (n-i-1) = \sum_{i=0}^{n-1} (i) = \frac{n(n-1)}{2} = O(N^2)$.