Data Structures & Algorithms: Time & Space Complexity Mastery

Key Concepts:

• Big-O Notation: Worst-case upper bound
• Omega (Ω): Best-case lower bound
• Theta (Θ): Tight bound (both upper and lower)

Common Complexity Classes:

Complexity Rules:

1. Drop constants: O(2n) → O(n)
2. Drop non-dominant terms: O(n² + n) → O(n²)
3. Different inputs → different variables: O(a + b)
4. Nested loops multiply: O(n * m)

Code Analysis Examples:

def get_first(arr):
    return arr[0]  # Single operation

def find_max(arr):
    max = arr[0]
    for num in arr:  # n operations
        if num > max:
            max = num
    return max

def bubble_sort(arr):
    for i in range(len(arr)):          # n iterations
        for j in range(len(arr)-1):    # n iterations
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

Algorithm Complexity Guide:

Memory Usage Cases:

def sum_pair(arr, target):
    hashset = set()  # Fixed size
    for num in arr:
        if target - num in hashset:
            return True
        hashset.add(num)
    return False

def reverse(arr):
    result = []       # Grows with input
    for i in range(len(arr)-1, -1, -1):
        result.append(arr[i])
    return result

Recursive Space Complexity:

# O(n) space due to call stack
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n-1)

# Tail recursion (O(1) with optimization)
def factorial_tail(n, acc=1):
    if n <= 1:
        return acc
    return factorial_tail(n-1, n*acc)