DSA Interview Prep · Lesson

Big-O Notation from Scratch

Understand why we care about asymptotic growth, how to drop constants and lower-order terms, and how to read Big-O at a glance.

Why Measure Algorithm Efficiency?

Two programs can both be correct, yet one finishes in a blink and the other runs for hours. Time complexity describes how runtime grows as the input gets bigger.

# O(n) approach
def find_max_linear(nums):
    m = nums[0]
    for n in nums:
        if n > m: m = n
    return m

# O(n^2) approach (unnecessary double loop)
def find_max_quadratic(nums):
    for i in range(len(nums)):
        is_max = all(nums[i] >= nums[j] for j in range(len(nums)))
        if is_max: return nums[i]

print(find_max_linear([3, 1, 4, 1, 5, 9]))  # 9

Big-O: Asymptotic Upper Bound

Big-O describes the worst-case upper bound on how fast cost grows. The trick: drop constants and smaller terms, because only the dominant term matters at scale. See the code.

# T(n) = 3n^2 + 5n + 100 is O(n^2)
# because the n^2 term dominates for large n

# T(n) = 2n + 1000 is O(n)
# the constant 1000 becomes negligible

# Rule: drop constants and lower-order terms
# 5n^3 + 2n^2 + n + 1  =>  O(n^3)
# 100 * log(n) + n      =>  O(n)
print('O(n^2) example: counting iterations')
n = 1000
count = sum(1 for i in range(n) for j in range(n))
print(count)  # 1_000_000 = n^2

All lessons in this course

← Back to DSA Interview Prep