Time and Space Complexity Refresher

1
Operations (relative growth)
2
^
3
|                  O(n!)
4
|                /
5
|             O(2ⁿ)
6
|           /
7
|        O(n³)
8
|      /
9
|    O(n²)
10
|   /
11
| O(n log n)
12
|/
13
|  O(n)
14
|   \
15
|    \
16
|     O(log n)
17
|      \
18
|       \______________________________> Input size (n)
19
|         O(1)

1
def get_first_element(arr):
2
    """O(1) - Always takes the same time"""
3
    if len(arr) > 0:
4
        return arr[0]
5
    return None
6

7
def hash_table_lookup(hash_table, key):
8
    """O(1) - Hash table access"""
9
    return hash_table.get(key)
10

11
def add_to_beginning(linked_list, value):
12
    """O(1) - Adding to front of linked list"""
13
    new_node = Node(value)
14
    new_node.next = linked_list.head
15
    linked_list.head = new_node

1
def binary_search(arr, target):
2
    """O(log n) - Divides search space in half each iteration"""
3
    left, right = 0, len(arr) - 1
4

5
    while left <= right:
6
        mid = (left + right) // 2
7
        if arr[mid] == target:
8
            return mid
9
        elif arr[mid] < target:
10
            left = mid + 1
11
        else:
12
            right = mid - 1
13

14
    return -1
15

16
def find_height(binary_tree_node):
17
    """O(log n) for balanced tree"""
18
    if not binary_tree_node:
19
        return 0
20
    return 1 + max(find_height(binary_tree_node.left),
21
                   find_height(binary_tree_node.right))

1
def linear_search(arr, target):
2
    """O(n) - May need to check every element"""
3
    for i, element in enumerate(arr):
4
        if element == target:
5
            return i
6
    return -1
7

8
def find_max(arr):
9
    """O(n) - Must check every element"""
10
    if not arr:
11
        return None
12

13
    max_val = arr[0]
14
    for num in arr[1:]:
15
        if num > max_val:
16
            max_val = num
17
    return max_val
18

19
def count_occurrences(arr, target):
20
    """O(n) - Count how many times target appears"""
21
    count = 0
22
    for element in arr:
23
        if element == target:
24
            count += 1
25
    return count

1
def merge_sort(arr):
2
    """O(n log n) - Divide and conquer sorting"""
3
    if len(arr) <= 1:
4
        return arr
5

6
    mid = len(arr) // 2
7
    left = merge_sort(arr[:mid])    # O(log n) levels
8
    right = merge_sort(arr[mid:])   # O(log n) levels
9

10
    return merge(left, right)       # O(n) work per level
11

12
def merge(left, right):
13
    """O(n) - Merge two sorted arrays"""
14
    result = []
15
    i = j = 0
16

17
    while i < len(left) and j < len(right):
18
        if left[i] <= right[j]:
19
            result.append(left[i])
20
            i += 1
21
        else:
22
            result.append(right[j])
23
            j += 1
24

25
    result.extend(left[i:])
26
    result.extend(right[j:])
27
    return result
28

29
def heap_sort(arr):
30
    """O(n log n) - Build heap then extract elements"""
31
    import heapq
32
    heapq.heapify(arr)              # O(n)
33
    sorted_arr = []
34
    while arr:
35
        sorted_arr.append(heapq.heappop(arr))  # O(log n) × n times
36
    return sorted_arr

1
def bubble_sort(arr):
2
    """O(n²) - Nested loops over array"""
3
    n = len(arr)
4
    for i in range(n):              # Outer loop: n iterations
5
        for j in range(0, n - i - 1):  # Inner loop: up to n iterations
6
            if arr[j] > arr[j + 1]:
7
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
8
    return arr
9

10
def find_all_pairs(arr):
11
    """O(n²) - Generate all possible pairs"""
12
    pairs = []
13
    for i in range(len(arr)):       # n iterations
14
        for j in range(i + 1, len(arr)):  # up to n iterations
15
            pairs.append((arr[i], arr[j]))
16
    return pairs
17

18
def naive_string_matching(text, pattern):
19
    """O(nm) where n=len(text), m=len(pattern)"""
20
    matches = []
21
    for i in range(len(text) - len(pattern) + 1):
22
        if text[i:i+len(pattern)] == pattern:
23
            matches.append(i)
24
    return matches

1
def fibonacci_recursive(n):
2
    """O(2ⁿ) - Naive recursive approach"""
3
    if n <= 1:
4
        return n
5
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
6

7
def generate_all_subsets(arr):
8
    """O(2ⁿ) - Generate all possible subsets"""
9
    def backtrack(start, current_subset):
10
        result.append(current_subset[:])  # Add current subset
11

12
        for i in range(start, len(arr)):
13
            current_subset.append(arr[i])  # Include element
14
            backtrack(i + 1, current_subset)
15
            current_subset.pop()           # Exclude element
16

17
    result = []
18
    backtrack(0, [])
19
    return result
20

21
def solve_n_queens(n):
22
    """O(n!) but often analyzed as exponential"""
23
    def is_safe(board, row, col):
24
        # Check column
25
        for i in range(row):
26
            if board[i][col] == 1:
27
                return False
28

29
        # Check diagonals
30
        for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
31
            if board[i][j] == 1:
32
                return False
33

34
        for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
35
            if board[i][j] == 1:
36
                return False
37

38
        return True
39

40
    def solve(board, row):
41
        if row >= n:
42
            return True
43

44
        for col in range(n):
45
            if is_safe(board, row, col):
46
                board[row][col] = 1
47
                if solve(board, row + 1):
48
                    return True
49
                board[row][col] = 0
50

51
        return False
52

53
    board = [[0 for _ in range(n)] for _ in range(n)]
54
    solve(board, 0)
55
    return board

1
def reverse_array_in_place(arr):
2
    """O(1) space - Only uses a few variables"""
3
    left = 0
4
    right = len(arr) - 1
5

6
    while left < right:
7
        arr[left], arr[right] = arr[right], arr[left]
8
        left += 1
9
        right -= 1
10

11
    return arr
12

13
def find_max_iterative(arr):
14
    """O(1) space - Only stores max value"""
15
    if not arr:
16
        return None
17

18
    max_val = arr[0]
19
    for num in arr:
20
        if num > max_val:
21
            max_val = num
22
    return max_val

1
def binary_search_recursive(arr, target, left=0, right=None):
2
    """O(log n) space - Recursive call stack"""
3
    if right is None:
4
        right = len(arr) - 1
5

6
    if left > right:
7
        return -1
8

9
    mid = (left + right) // 2
10
    if arr[mid] == target:
11
        return mid
12
    elif arr[mid] < target:
13
        return binary_search_recursive(arr, target, mid + 1, right)
14
    else:
15
        return binary_search_recursive(arr, target, left, mid - 1)
16

17
def calculate_height(node):
18
    """O(log n) space for balanced tree - call stack"""
19
    if not node:
20
        return 0
21
    return 1 + max(calculate_height(node.left),
22
                   calculate_height(node.right))

1
def merge_sort(arr):
2
    """O(n) space - Creates new arrays for merging"""
3
    if len(arr) <= 1:
4
        return arr
5

6
    mid = len(arr) // 2
7
    left = merge_sort(arr[:mid])    # O(n) space for new arrays
8
    right = merge_sort(arr[mid:])   # O(n) space for new arrays
9

10
    return merge(left, right)
11

12
def fibonacci_dp(n):
13
    """O(n) space - Stores all intermediate results"""
14
    if n <= 1:
15
        return n
16

17
    dp = [0] * (n + 1)
18
    dp[1] = 1
19

20
    for i in range(2, n + 1):
21
        dp[i] = dp[i - 1] + dp[i - 2]
22

23
    return dp[n]
24

25
def level_order_traversal(root):
26
    """O(n) space - Queue can hold up to n/2 nodes"""
27
    if not root:
28
        return []
29

30
    queue = [root]
31
    result = []
32

33
    while queue:
34
        node = queue.pop(0)
35
        result.append(node.val)
36

37
        if node.left:
38
            queue.append(node.left)
39
        if node.right:
40
            queue.append(node.right)
41

42
    return result

1
def floyd_warshall(graph):
2
    """O(n²) space - 2D distance matrix"""
3
    n = len(graph)
4
    dist = [[float('inf')] * n for _ in range(n)]
5

6
    # Initialize distances
7
    for i in range(n):
8
        for j in range(n):
9
            if i == j:
10
                dist[i][j] = 0
11
            elif graph[i][j] != 0:
12
                dist[i][j] = graph[i][j]
13

14
    # Floyd-Warshall algorithm
15
    for k in range(n):
16
        for i in range(n):
17
            for j in range(n):
18
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
19

20
    return dist
21

22
def generate_multiplication_table(n):
23
    """O(n²) space - 2D table"""
24
    table = []
25
    for i in range(1, n + 1):
26
        row = []
27
        for j in range(1, n + 1):
28
            row.append(i * j)
29
        table.append(row)
30
    return table

1
# Array operations examples
2
def array_operations():
3
    arr = [1, 2, 3, 4, 5]
4

5
    # O(1) access
6
    element = arr[2]
7

8
    # O(n) search
9
    index = arr.index(3) if 3 in arr else -1
10

11
    # O(1) append
12
    arr.append(6)
13

14
    # O(n) insert at beginning
15
    arr.insert(0, 0)
16

17
    # O(1) pop from end
18
    arr.pop()
19

20
    # O(n) pop from beginning
21
    arr.pop(0)

1
class ListNode:
2
    def __init__(self, val=0, next=None):
3
        self.val = val
4
        self.next = next
5

6
class LinkedList:
7
    def __init__(self):
8
        self.head = None
9

10
    def insert_at_beginning(self, val):
11
        """O(1) time, O(1) space"""
12
        new_node = ListNode(val)
13
        new_node.next = self.head
14
        self.head = new_node
15

16
    def search(self, val):
17
        """O(n) time, O(1) space"""
18
        current = self.head
19
        while current:
20
            if current.val == val:
21
                return current
22
            current = current.next
23
        return None
24

25
    def delete(self, val):
26
        """O(n) time, O(1) space"""
27
        if not self.head:
28
            return
29

30
        if self.head.val == val:
31
            self.head = self.head.next
32
            return
33

34
        current = self.head
35
        while current.next:
36
            if current.next.val == val:
37
                current.next = current.next.next
38
                return
39
            current = current.next

1
class HashTable:
2
    def __init__(self, size=10):
3
        self.size = size
4
        self.table = [[] for _ in range(size)]
5

6
    def _hash(self, key):
7
        """Simple hash function"""
8
        return hash(key) % self.size
9

10
    def insert(self, key, value):
11
        """O(1) average, O(n) worst case"""
12
        index = self._hash(key)
13
        bucket = self.table[index]
14

15
        for i, (k, v) in enumerate(bucket):
16
            if k == key:
17
                bucket[i] = (key, value)
18
                return
19

20
        bucket.append((key, value))
21

22
    def get(self, key):
23
        """O(1) average, O(n) worst case"""
24
        index = self._hash(key)
25
        bucket = self.table[index]
26

27
        for k, v in bucket:
28
            if k == key:
29
                return v
30

31
        raise KeyError(key)

1
class TreeNode:
2
    def __init__(self, val=0, left=None, right=None):
3
        self.val = val
4
        self.left = left
5
        self.right = right
6

7
class BST:
8
    def __init__(self):
9
        self.root = None
10

11
    def insert(self, val):
12
        """O(log n) average, O(n) worst case time; O(log n) space"""
13
        def insert_recursive(node, val):
14
            if not node:
15
                return TreeNode(val)
16

17
            if val < node.val:
18
                node.left = insert_recursive(node.left, val)
19
            else:
20
                node.right = insert_recursive(node.right, val)
21

22
            return node
23

24
        self.root = insert_recursive(self.root, val)
25

26
    def search(self, val):
27
        """O(log n) average, O(n) worst case time; O(log n) space"""
28
        def search_recursive(node, val):
29
            if not node or node.val == val:
30
                return node
31

32
            if val < node.val:
33
                return search_recursive(node.left, val)
34
            else:
35
                return search_recursive(node.right, val)
36

37
        return search_recursive(self.root, val)

1
def bubble_sort(arr):
2
    """
3
    Time: O(n²) average and worst, O(n) best
4
    Space: O(1)
5
    """
6
    n = len(arr)
7
    for i in range(n):
8
        swapped = False
9
        for j in range(0, n - i - 1):
10
            if arr[j] > arr[j + 1]:
11
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
12
                swapped = True
13

14
        if not swapped:  # Early termination for best case
15
            break
16

17
    return arr
18

19
def merge_sort(arr):
20
    """
21
    Time: O(n log n) all cases
22
    Space: O(n)
23
    """
24
    if len(arr) <= 1:
25
        return arr
26

27
    mid = len(arr) // 2
28
    left = merge_sort(arr[:mid])
29
    right = merge_sort(arr[mid:])
30

31
    return merge(left, right)
32

33
def quick_sort(arr):
34
    """
35
    Time: O(n log n) average, O(n²) worst
36
    Space: O(log n) average, O(n) worst
37
    """
38
    if len(arr) <= 1:
39
        return arr
40

41
    pivot = arr[len(arr) // 2]
42
    left = [x for x in arr if x < pivot]
43
    middle = [x for x in arr if x == pivot]
44
    right = [x for x in arr if x > pivot]
45

46
    return quick_sort(left) + middle + quick_sort(right)

1
def linear_search(arr, target):
2
    """
3
    Time: O(n)
4
    Space: O(1)
5
    """
6
    for i, element in enumerate(arr):
7
        if element == target:
8
            return i
9
    return -1
10

11
def binary_search(arr, target):
12
    """
13
    Time: O(log n)
14
    Space: O(1) iterative, O(log n) recursive
15
    """
16
    left, right = 0, len(arr) - 1
17

18
    while left <= right:
19
        mid = (left + right) // 2
20
        if arr[mid] == target:
21
            return mid
22
        elif arr[mid] < target:
23
            left = mid + 1
24
        else:
25
            right = mid - 1
26

27
    return -1
28

29
def depth_first_search(graph, start, target):
30
    """
31
    Time: O(V + E) where V = vertices, E = edges
32
    Space: O(V) for recursion stack
33
    """
34
    def dfs(node, visited):
35
        if node == target:
36
            return True
37

38
        visited.add(node)
39
        for neighbor in graph[node]:
40
            if neighbor not in visited:
41
                if dfs(neighbor, visited):
42
                    return True
43

44
        return False
45

46
    return dfs(start, set())
47

48
def breadth_first_search(graph, start, target):
49
    """
50
    Time: O(V + E)
51
    Space: O(V) for queue
52
    """
53
    from collections import deque
54

55
    queue = deque([start])
56
    visited = {start}
57

58
    while queue:
59
        node = queue.popleft()
60
        if node == target:
61
            return True
62

63
        for neighbor in graph[node]:
64
            if neighbor not in visited:
65
                visited.add(neighbor)
66
                queue.append(neighbor)
67

68
    return False

1
def fibonacci_recursive(n):
2
    """
3
    Time: O(2ⁿ) - Exponential without memoization
4
    Space: O(n) - Recursion stack
5
    """
6
    if n <= 1:
7
        return n
8
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
9

10
def fibonacci_memoized(n, memo={}):
11
    """
12
    Time: O(n) - Each subproblem solved once
13
    Space: O(n) - Memoization table + recursion stack
14
    """
15
    if n in memo:
16
        return memo[n]
17

18
    if n <= 1:
19
        return n
20

21
    memo[n] = fibonacci_memoized(n - 1, memo) + fibonacci_memoized(n - 2, memo)
22
    return memo[n]
23

24
def fibonacci_tabulation(n):
25
    """
26
    Time: O(n) - Single loop
27
    Space: O(n) - DP table
28
    """
29
    if n <= 1:
30
        return n
31

32
    dp = [0] * (n + 1)
33
    dp[1] = 1
34

35
    for i in range(2, n + 1):
36
        dp[i] = dp[i - 1] + dp[i - 2]
37

38
    return dp[n]
39

40
def fibonacci_optimized(n):
41
    """
42
    Time: O(n)
43
    Space: O(1) - Only store last two values
44
    """
45
    if n <= 1:
46
        return n
47

48
    prev2, prev1 = 0, 1
49

50
    for i in range(2, n + 1):
51
        current = prev1 + prev2
52
        prev2, prev1 = prev1, current
53

54
    return prev1

1
def example_1(arr):
2
    """
3
    Analysis:
4
    - Single loop: n iterations
5
    - Constant work per iteration: O(1)
6
    - Total: O(n) × O(1) = O(n)
7
    """
8
    total = 0                    # O(1)
9
    for num in arr:              # O(n)
10
        total += num             # O(1)
11
    return total                 # O(1)
12
    # Overall: O(n)
13

14
def example_2(arr):
15
    """
16
    Analysis:
17
    - Outer loop: n iterations
18
    - Inner loop: n iterations per outer iteration
19
    - Total: O(n) × O(n) = O(n²)
20
    """
21
    for i in range(len(arr)):    # O(n)
22
        for j in range(len(arr)): # O(n)
23
            print(arr[i] + arr[j]) # O(1)
24
    # Overall: O(n²)
25

26
def example_3(arr):
27
    """
28
    Analysis:
29
    - First loop: O(n)
30
    - Second loop: O(n)
31
    - Total: O(n) + O(n) = O(n)
32
    """
33
    # First pass
34
    for num in arr:              # O(n)
35
        print(num)               # O(1)
36

37
    # Second pass
38
    for num in arr:              # O(n)
39
        print(num * 2)           # O(1)
40

41
    # Overall: O(n) + O(n) = O(n)
42

43
def example_4(arr):
44
    """
45
    Analysis:
46
    - Outer loop: n iterations
47
    - Inner loop: i iterations (0, 1, 2, ..., n-1)
48
    - Total: 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n²)
49
    """
50
    for i in range(len(arr)):    # O(n)
51
        for j in range(i):       # O(i), average O(n/2)
52
            print(arr[i], arr[j]) # O(1)
53
    # Overall: O(n²)
54

55
def example_5(arr, target):
56
    """
57
    Analysis:
58
    - While loop divides array in half each iteration
59
    - Maximum log₂(n) iterations
60
    - Constant work per iteration
61
    - Total: O(log n)
62
    """
63
    left, right = 0, len(arr) - 1
64

65
    while left <= right:         # O(log n)
66
        mid = (left + right) // 2 # O(1)
67
        if arr[mid] == target:   # O(1)
68
            return mid           # O(1)
69
        elif arr[mid] < target:  # O(1)
70
            left = mid + 1       # O(1)
71
        else:                    # O(1)
72
            right = mid - 1      # O(1)
73

74
    return -1                    # O(1)
75
    # Overall: O(log n)

1
# Slow: O(n) lookup in list
2
def find_in_list(items, target):
3
    return target in items  # O(n)
4

5
# Fast: O(1) average lookup in set
6
def find_in_set(items_set, target):
7
    return target in items_set  # O(1) average
8

9
# Example usage
10
items = [1, 2, 3, 4, 5] * 1000
11
items_set = set(items)
12

13
# O(n) vs O(1) lookup time

1
# Without memoization: O(2ⁿ)
2
def fibonacci_slow(n):
3
    if n <= 1:
4
        return n
5
    return fibonacci_slow(n - 1) + fibonacci_slow(n - 2)
6

7
# With memoization: O(n)
8
def fibonacci_fast(n, memo={}):
9
    if n in memo:
10
        return memo[n]
11
    if n <= 1:
12
        return n
13
    memo[n] = fibonacci_fast(n - 1, memo) + fibonacci_fast(n - 2, memo)
14
    return memo[n]

1
# Naive approach: O(n²)
2
def find_pair_sum_slow(arr, target):
3
    for i in range(len(arr)):
4
        for j in range(i + 1, len(arr)):
5
            if arr[i] + arr[j] == target:
6
                return (i, j)
7
    return None
8

9
# Optimized approach: O(n) for sorted arrays
10
def find_pair_sum_fast(arr, target):
11
    left, right = 0, len(arr) - 1
12
    while left < right:
13
        current = arr[left] + arr[right]
14
        if current == target:
15
            return (left, right)
16
        if current < target:
17
            left += 1
18
        else:
19
            right -= 1
20
    return None