DSA Interview Prep · Lesson

Analysing Loops and Nested Loops

Calculate time complexity for single loops, nested loops, and loops with shrinking ranges such as binary search or triangle iterations.

Single Loop: O(n)

The simplest loop runs its body n times, so it is O(n). A bigger step changes the count but not the class. Always start by counting how often the body runs. See the code.

# O(n): body runs n times
def count_ops_linear(n):
    ops = 0
    for i in range(n):
        ops += 1     # constant work
    return ops

print(count_ops_linear(100))  # 100

# Still O(n): step=2 halves count but same class
def count_ops_half(n):
    ops = 0
    for i in range(0, n, 2):
        ops += 1
    return ops

print(count_ops_half(100))    # 50  => O(n)

Nested Loops: O(n²) and Beyond

Two loops nested, each n times, give n x n = O(n^2); three give O(n^3). But if the inner loop runs a fixed number of times, the whole thing stays linear.

def count_pairs(n):
    ops = 0
    for i in range(n):          # n iterations
        for j in range(n):      # n iterations each
            ops += 1
    return ops

print(count_pairs(10))   # 100 = 10^2
print(count_pairs(100))  # 10000 = 100^2
# Doubling n quadruples ops: classic O(n^2)

All lessons in this course

← Back to DSA Interview Prep