Big O Practice: Half Bound Nested

def count_smaller_pairs(arr):
    count = 0
    n = len(arr)
    for i in range(n):
        for j in range(i):
            if arr[j] < arr[i]:
                count += 1
    return count

Variables

• n - length of the input array

Explanation

It looks like "half" of a quadratic loop because `j < i`, but the total comparisons are `0 + 1 + ... + (n-1) = n(n-1)/2` which is still **O(n²)** after dropping the constant. Space is **O(1)**.

More Big O practice problems · Today's daily problem