Big-O Complexity Hierarchy
Big-O order: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
Big-O Complexity Hierarchy
From fastest to slowest — know this order cold
O(1): constant, always same speed. O(log n): binary search. O(n): one scan. O(n log n): merge sort. O(n²): nested loops. O(2ⁿ): brute force combinations. Choose lowest complexity when possible.
Binary Search
Binary search: sorted array, cut in half each time → O(log n)
Binary Search
How binary search works and why it's dramatically faster than linear search
Start in the middle. Is target higher or lower? Eliminate half. Repeat. 1 million items → max 20 comparisons. Requires sorted data.
Sorting Algorithms
Bubble O(n²), Merge O(n log n) always, Quick O(n log n) average
Sorting Algorithms
Three essential sorting algorithms and their complexities
Bubble sort: compare adjacent pairs, swap — simple but slow. Merge sort: divide and conquer, always O(n log n), stable. Quick sort: partition around pivot, O(n log n) average but O(n²) worst case.
Algorithm Paradigms
Greedy: local best choice. Dynamic Programming: cache overlapping subproblems.
Algorithm Paradigms
Two major approaches to optimization problems
Greedy: always pick locally optimal — works for some problems (Dijkstra's, Huffman coding). Dynamic programming: break into overlapping subproblems, cache results — works for more complex problems (knapsack, Fibonacci).
Two-Pointer Technique
Two-pointer technique: O(n) solution for sorted array problems — move inward from both ends
Two-Pointer Technique
A powerful O(n) strategy for many array and string problems
Place one pointer at start, one at end. Move inward based on condition. Finds pairs that sum to target in O(n) instead of O(n²). Also used for: removing duplicates, palindrome check, container with most water.
Divide and Conquer
Divide and conquer: split problem in half, solve each half, combine. Merge sort, binary search, FFT.
Divide and Conquer
Breaking problems into smaller subproblems recursively
Three steps: Divide (split into subproblems), Conquer (solve recursively), Combine (merge solutions). Merge sort: split array in half, sort each half, merge → O(n log n). Binary search: split search space in half each time → O(log n). Master Theorem gives recurrence time complexity.
Shortest Path Algorithms
BFS: shortest path in unweighted graph, uses queue. Dijkstra: shortest path with weights, uses priority queue.
Shortest Path Algorithms
Finding the fastest route through a graph
BFS (Breadth-First Search): finds shortest path in unweighted graphs — explores level by level. Dijkstra's algorithm: shortest path in weighted graphs with non-negative weights — uses a min-priority queue, greedy approach. Bellman-Ford: handles negative weights, detects negative cycles — O(VE).
Memoization
Space-time tradeoff: memoization stores results to avoid recomputation — uses more memory, saves time
Memoization
Caching function results to avoid redundant computation
Memoization: store results of expensive function calls, return cached result when same inputs occur again. Top-down dynamic programming. Fibonacci: naive recursive = O(2ⁿ), memoized = O(n). Trade: O(n) extra space for O(n) time instead of O(2ⁿ). Key insight: avoid recomputing overlapping subproblems.
Sliding Window Technique
Sliding window: maintain a window of elements, slide it across array — O(n) instead of O(n²)
Sliding Window Technique
Efficiently solving subarray/substring problems
Fixed window: maintain window of size k, add one element, remove one element each step. Variable window: expand/contract window based on condition. Problems: maximum sum subarray of size k, longest substring without repeating characters. Avoids nested loops — O(n) instead of O(n²).
Recursion vs Iteration
Recursion vs iteration: recursion elegant but uses call stack. Deep recursion can cause stack overflow.
Recursion vs Iteration
When to recurse and when to loop
Recursion: elegant, mirrors mathematical definition, natural for tree/graph problems. Call stack has limited size — deep recursion → stack overflow. Tail recursion: recursive call is the last operation — some languages optimize this. Iteration: explicit stack management, more memory-efficient, sometimes harder to read.
P vs NP
NP-hard problems: no known polynomial solution. Traveling salesman, knapsack, graph coloring.
P vs NP
The most important unsolved problem in computer science
P: problems solvable in polynomial time. NP: solutions verifiable in polynomial time. NP-complete: hardest problems in NP. P=NP?: if any NP-complete problem has a polynomial solution, all do. Most believe P≠NP. Practical: use approximation algorithms or heuristics for NP-hard problems.
Amortized Analysis
Amortized analysis: occasional expensive operations averaged over many cheap ones — ArrayList doubling
Amortized Analysis
Why some data structures are efficient despite occasional slow operations
ArrayList/dynamic array: usually O(1) append, occasionally O(n) when resizing (copies all elements to new array). But doubling strategy means O(n) happens rarely — amortized O(1) per append. Stack push/pop: amortized O(1). Amortized analysis considers the average cost over a sequence of operations.