Data Structures & Algorithms

Problem: Find the largest number in a list

Algorithm:
1. Assume first element is largest
2. Compare with each remaining element
3. If current element is bigger, update largest
4. After checking all, return largest

This is O(n) — we look at each element once

# Example: Two approaches to find duplicates

# Approach 1: Brute Force — O(n²) time, O(1) space
def has_duplicate_v1(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

# Approach 2: Hash Set — O(n) time, O(n) space
def has_duplicate_v2(arr):
    seen = set()
    for num in arr:
        if num in seen:
            return True
        seen.add(num)
    return False

# V2 is FASTER but uses MORE MEMORY — classic trade-off!

Example: Linear Search

Best case:  Ω(1)      — Found at index 0
Worst case: O(n)      — Found at last index (or not found)
Average:    Θ(n/2) = Θ(n)  — Found somewhere in the middle

When we say "Linear Search is O(n)" we mean:
→ In the WORST case, it checks all n elements

FAST ────────────────────────────────────── SLOW

O(1)  O(log n)  O(n)  O(n log n)  O(n²)  O(2^n)  O(n!)
 │       │       │       │          │       │       │
 ▼       ▼       ▼       ▼          ▼       ▼       ▼
Const  Logarith Linear Linearith Quadra  Expon  Factor

# This is O(n), NOT O(3n)
for i in range(n):     # n operations
    print(i)
for i in range(n):     # + n operations
    print(i)
for i in range(n):     # + n operations
    print(i)
# Total: 3n → O(n)

# This is O(n²), NOT O(n² + n)
for i in range(n):           # O(n²)
    for j in range(n):
        print(i, j)

for k in range(n):           # + O(n)
    print(k)

# Total: n² + n → O(n²)  (n² dominates)

for i in range(n):       # n ×
    for j in range(n):   # n ×
        for k in range(n): # n
            print(i, j, k)
# Total: n × n × n = O(n³)

def example(n):
    # Block 1: O(n)
    for i in range(n):
        print(i)
    
    # Block 2: O(n²)
    for i in range(n):
        for j in range(n):
            print(i, j)
    
    # Total: O(n) + O(n²) = O(n²)

# Each step halves the input → O(log n)
i = n
while i > 1:
    i = i // 2  # Halving each time!
    print(i)

# For n = 1000: only ~10 steps (log₂ 1000 ≈ 10)

# O(1) space — uses fixed variables
def sum_array(arr):
    total = 0
    for num in arr:
        total += num
    return total

# O(n) space — creates a new array of size n
def double_array(arr):
    result = []
    for num in arr:
        result.append(num * 2)
    return result

# O(n) space — recursion uses call stack
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)  # n stack frames!

# O(1) — Constant
x = arr[5]

# O(log n) — Halving
while n > 1: n //= 2

# O(n) — Single loop
for x in arr: print(x)

# O(n²) — Nested loop
for i in arr:
    for j in arr: print(i, j)