Algorithm tricks that make Big-O click

Binary search: sorted array, cut in half each time → O(log n)

Binary Search — Start in the middle. Is target higher or lower? Eliminate half. Repeat. 1 million items → max 20 comparisons. Requires sorted data.

Big-O order: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

Big-O Complexity Hierarchy — 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.

Bubble O(n²), Merge O(n log n) always, Quick O(n log n) average

Sorting Algorithms — 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.

Greedy: local best choice. Dynamic Programming: cache overlapping subproblems.

Algorithm Paradigms — 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: O(n) solution for sorted array problems — move inward from both ends

Two-Pointer Technique — 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: split problem in half, solve each half, combine. Merge sort, binary search, FFT.

Divide and Conquer — 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.

BFS (Breadth-First Search): shortest path in unweighted graph, uses queue. Dijkstra: shortest path with weights, uses priority queue.

Shortest Path Algorithms — 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).

Space-time tradeoff: memoization stores results to avoid recomputation — uses more memory, saves time

Memoization — 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: maintain a window of elements, slide it across array — O(n) instead of O(n²)

Sliding Window Technique — 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 elegant but uses call stack. Deep recursion can cause stack overflow.

Recursion vs Iteration — 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.

NP-hard (Non-deterministic Polynomial-time hard) problems: no known polynomial solution. Traveling salesman, knapsack, graph coloring.

P vs NP — 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: occasional expensive operations averaged over many cheap ones — ArrayList doubling

Amortized Analysis — 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.