Algorithm Analysis - Big O Notation, Complexity

Introduction

Algorithm analysis is the process of evaluating the performance of an algorithm in terms of time and space complexity. Big O notation provides a standardized way to describe how an algorithm's performance scales as the input size grows.

Time Complexity

Time complexity describes how the runtime of an algorithm grows with input size.

# O(1) - Constant Time
def get_first_element(arr):
    return arr[0] if arr else None

# O(log n) - Logarithmic Time
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# O(n) - Linear Time
def find_max(arr):
    max_val = arr[0]
    for num in arr:
        if num > max_val:
            max_val = num
    return max_val

# O(n log n) - Linearithmic Time
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# O(n²) - Quadratic Time
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# O(2^n) - Exponential Time
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Space Complexity

Space complexity describes how much additional memory an algorithm needs.

# O(1) Space
def sum_array(arr):
    total = 0
    for num in arr:
        total += num
    return total

# O(n) Space
def reverse_array(arr):
    return arr[::-1]

# O(n) Space (recursion stack)
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

# O(log n) Space
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

Common Complexities Comparison

import time

def benchmark(func, *args):
    start = time.time()
    result = func(*args)
    end = time.time()
    return result, end - start

# Comparing different complexities
def constant_operation(n):
    return n * 2

def logarithmic_operation(n):
    result = 0
    while n > 0:
        n //= 2
        result += 1
    return result

def linear_operation(n):
    return sum(range(n))

def quadratic_operation(n):
    return sum(i * j for i in range(n) for j in range(n))

sizes = [10, 100, 1000, 10000]
for size in sizes:
    print(f"n={size}")
    print(f"  O(1): {benchmark(constant_operation, size)[1]:.6f}")
    print(f"  O(log n): {benchmark(logarithmic_operation, size)[1]:.6f}")
    print(f"  O(n): {benchmark(linear_operation, size)[1]:.6f}")

Practice Problems

1. Analyze the time complexity of a given code snippet.
2. Calculate the space complexity of a recursive algorithm.
3. Compare O(n) and O(n²) algorithms for different input sizes.
4. Optimize an O(n²) algorithm to O(n log n).
5. Determine the best, average, and worst-case complexity of an algorithm.