Understanding Big O Notation

O(n) = "order n"
O(n²) = "order n squared"

# Always one operation
def first_element(arr):
    return arr[0]

# Binary search
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
```python

### O(n) - Linear

```python
# Single loop
def find_max(arr):
    max_val = arr[0]
    for num in arr:
        if num > max_val:
            max_val = num
    return max_val

# Sorting: merge sort, heap sort
# Most efficient comparison sorts
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)
```python

### O(n²) - Quadratic

```python
# Nested loops
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]

# Recursive without memoization
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)
```python

### O(n!) - Factorial

```python
# Permutations
def permutations(arr):
    if len(arr) <= 1:
        return [arr]
    
    result = []
    for i, element in enumerate(arr):
        remaining = arr[:i] + arr[i+1:]
        for p in permutations(remaining):
            result.append([element] + p)
    
    return result

def sum_arr(arr):
    total = 0  # One variable
    for num in arr:
        total += num
    return total
```python

### O(n) - Linear

```python
def double_arr(arr):
    return [x * 2 for x in arr]  # New array

# O(n) + O(n) = O(n)
def example1(n):
    for i in range(n):
        print(i)
    for i in range(n):
        print(i)

# O(n²) + O(n) = O(n²)
def example2(n):
    for i in range(n):
        for j in range(n):
            print(i, j)
    for i in range(n):
        print(i)

# O(1) inside O(n) = O(n)
def example3(n):
    for i in range(n):
        x = i * 2  # O(1)
```python

## Common Patterns

### Loops

- Single loop: O(n)
- Two nested loops: O(n²)
- Loop with halving: O(log n)

### Recursion

- Single call: O(n)
- Binary tree recursion: O(2^n)

### Data Structures

| Operation | Array | Linked List | Hash Table |
|-----------|-------|-------------|------------|
| Access | O(1) | O(n) | O(1) |
| Search | O(n) | O(n) | O(1) |
| Insert | O(n) | O(1) | O(1) |
| Delete | O(n) | O(1) | O(1) |

## Practical Application

### Choose Algorithms

| Input Size | Use |
|-----------|------|
| < 1000 | O(n²) okay |
| < 100K | O(n log n) |
| < 10M | O(n) |
| 10M+ | O(log n), O(1) |

### Optimization

```python
# Before: O(n²)
def has_duplicates_bad(arr):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

# After: O(n)
def has_duplicates_good(arr):
    seen = set()
    for num in arr:
        if num in seen:
            return True
        seen.add(num)
    return False

# Real-world O(1) examples
def is_even(n):
    return n % 2 == 0

# Hash table lookup
def get_user_name(users, user_id):
    return users.get(user_id)  # O(1) average case

# Stack/queue operations
stack.append(item)   # O(1)
stack.pop()          # O(1)

# Balanced BST lookup
import bisect
def find_closest(sorted_arr, target):
    idx = bisect.bisect_left(sorted_arr, target)
    if idx == 0:
        return sorted_arr[0]
    if idx == len(sorted_arr):
        return sorted_arr[-1]
    before = sorted_arr[idx - 1]
    after = sorted_arr[idx]
    return before if target - before < after - target else after

# Exponentiation by squaring
def fast_power(base, exp):
    """O(log exp) vs O(exp) naive."""
    if exp == 0:
        return 1
    half = fast_power(base, exp // 2)
    return half * half * base if exp % 2 else half * half

# Linear time examples
def has_duplicate_linear(arr):
    """O(n) using hash set."""
    seen = set()
    for x in arr:
        if x in seen:
            return True
        seen.add(x)
    return False

# Counting frequencies
from collections import Counter
def most_frequent(arr):
    return Counter(arr).most_common(1)[0][0]

# Two-pointer technique
def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

# Sorting is the classic O(n log n) problem
import heapq

def heap_sort(arr):
    heapq.heapify(arr)
    return [heapq.heappop(arr) for _ in range(len(arr))]

# Partitioning for quickselect
def find_kth_largest(nums, k):
    """Quickselect: O(n) average, O(n²) worst."""
    return heapq.nlargest(k, nums)[-1]  # O(n log k)

# Many divide-and-conquer algorithms
def count_inversions(arr):
    """Count inversions using merge sort: O(n log n)."""
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, inv_left = count_inversions(arr[:mid])
    right, inv_right = count_inversions(arr[mid:])
    merged, inv_merge = merge_and_count(left, right)
    return merged, inv_left + inv_right + inv_merge

# Quadratic time examples
def naive_matrix_multiply(A, B):
    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):  # Triple nested = O(n³)
                C[i][j] += A[i][k] * B[k][j]
    return C

# All pairs shortest distance (naive)
def closest_pair_bruteforce(points):
    n = len(points)
    min_dist = float('inf')
    for i in range(n):
        for j in range(i + 1, n):
            dist = math.dist(points[i], points[j])
            min_dist = min(min_dist, dist)
    return min_dist

# Compare all elements
def has_duplicate_bruteforce(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

# Exponential time examples
def all_subsets(arr):
    """Generate all 2^n subsets."""
    if not arr:
        return [[]]
    subsets = all_subsets(arr[1:])
    return subsets + [[arr[0]] + s for s in subsets]

def fibonacci_exponential(n):
    """2^n without memoization."""
    if n <= 1:
        return n
    return fibonacci_exponential(n - 1) + fibonacci_exponential(n - 2)

# With memoization -> O(n)
def fibonacci_linear(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_linear(n - 1) + fibonacci_linear(n - 2)
    return memo[n]

# O(1) space: in-place modification
def reverse_array_in_place(arr):
    i, j = 0, len(arr) - 1
    while i < j:
        arr[i], arr[j] = arr[j], arr[i]
        i += 1
        j -= 1

# O(n) space: build a hash table
def find_missing_numbers(nums):
    """Returns missing numbers from 1..n."""
    present = set(nums)
    return [i for i in range(1, len(nums) + 1) if i not in present]

# O(n²) space: 2D DP table
def create_dp_table(n):
    return [[0] * n for _ in range(n)]

# O(log n) space: recursive binary search
def binary_search_rec(arr, target, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, high)
    return binary_search_rec(arr, target, low, mid - 1)

class DynamicArray:
    """Amortized analysis: O(1) append."""
    
    def __init__(self):
        self.capacity = 1
        self.arr = [None] * self.capacity
        self.size = 0
    
    def append(self, item):
        if self.size == self.capacity:
            # Resize: O(n) copy
            self.capacity *= 2
            new_arr = [None] * self.capacity
            for i in range(self.size):
                new_arr[i] = self.arr[i]
            self.arr = new_arr
        
        self.arr[self.size] = item
        self.size += 1

# Quicksort: worst case on already-sorted arrays with naive pivot
def quicksort_worst_case(arr):
    """Demonstrates O(n²) worst case with sorted input."""
    if len(arr) <= 1:
        return arr
    # Always picks last element as pivot -> worst case for sorted input
    pivot = arr[-1]
    left = [x for x in arr[:-1] if x <= pivot]
    right = [x for x in arr[:-1] if x > pivot]
    return quicksort_worst_case(left) + [pivot] + quicksort_worst_case(right)

# Use random pivot for O(n log n) average
import random
def quicksort_random(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort_random(left) + mid + quicksort_random(right)

# NP-complete: Subset Sum (verifiable in polynomial time)
def verify_subset_sum(nums, subset, target):
    """O(n) verification of subset sum solution."""
    return sum(nums[i] for i in subset) == target

# NP-hard: TSP (optimization) requires exponential time to solve exactly
def traveling_salesman_bruteforce(distances):
    """O(n!) exact TSP solution."""
    n = len(distances)
    cities = list(range(n))
    min_distance = float('inf')
    best_route = None
    
    import itertools
    for route in itertools.permutations(cities[1:]):
        route = (0,) + route + (0,)
        dist = sum(distances[route[i]][route[i+1]] for i in range(n))
        if dist < min_distance:
            min_distance = dist
            best_route = route
    
    return best_route, min_distance