
Binary Search vs Linear Search: One Condition Changes Everything
Binary search vs linear search: when O(log n) beats O(n), the midpoint overflow bug, crossover at n=100, and the loop invariant that controls your code.
Page 37 of 61 · Ideas for curious minds in tech.
Back to the archive
Binary search vs linear search: when O(log n) beats O(n), the midpoint overflow bug, crossover at n=100, and the loop invariant that controls your code.

Every tree is a graph, but the reverse is not true. The graph vs tree difference is two structural constraints that explain every coding interview DFS decision.

Quicksort vs merge sort: same O(n log n), opposite tradeoffs. Why quicksort wins in practice, when stability matters, and what real sort functions use.

Priority queue vs queue explained: FIFO gives O(1) with a circular buffer. A binary heap gives O(log n) and the minimum first. One question decides.

Trie vs suffix tree: one indexes a dictionary for prefix search, one indexes all substrings of a string. Choose wrong and your solution blows up to O(n²).

Merge sort vs heap sort: both run Θ(n log n), but merge sort is 2–4x faster. Learn why cache behavior and stability decide which to use.

Dijkstra vs Bellman-Ford: one negative edge decides it. Learn why Dijkstra fails on negative weights, how Bellman-Ford works, and when to use each.

Adjacency list vs adjacency matrix: the E vs V² ratio decides everything. Sparse graph traversal needs the list. Dense graphs and Floyd-Warshall need the matrix.

Segment tree vs sparse table: one handles updates, one doesn't. Full decision table, why idempotency matters, and the silent XOR trap explained.

Bloom filter vs hash set: the exact memory tradeoff, when 1% false positives save 10x RAM, and which to use in system design and DSA interviews.

LRU vs LFU cache eviction: O(1) implementations, when each fails, Redis allkeys-lru vs allkeys-lfu, ARC, W-TinyLFU, and a decision framework.

AVL vs red-black tree: height bounds derived from proofs, rotation cost on delete, and why AVL beats red-black 2x for sorted insertions.

B-tree vs binary search tree: why B-trees use wide nodes to cut disk reads from 30 to 4 levels, when each structure wins, and the height proof.

Segment tree vs Fenwick tree: the real decision is invertibility, not complexity. Both run O(log n). Here's when each one wins.

A queue vs deque comparison: why the second end matters for sliding window maximum, the Python list.pop(0) trap, and how to choose between them.

Singly linked list vs doubly linked list: one pointer changes O(1) vs O(n) deletion. Full comparison, time complexity table, and LRU cache.

Trie vs hash map: both are O(k) for string keys, but only a trie answers prefix queries in O(p+m). Learn when each wins and why it matters in interviews.

Heap vs sorted array: heap insertion is O(log n), sorted array insertion is O(n). The complexity breakdown and the one question that decides it.

Heap vs binary search tree: both O(log n) insert, completely different capabilities. When to use each, with complexity tables, code, and diagrams.

BST vs hash map: when O(log n) range queries, floor/ceiling, and min/max beat O(1) point lookups in coding interviews and real systems.

HashSet vs TreeSet comes down to one question: do you need nearest-element queries? Performance, memory, and interview patterns compared.

HashMap vs TreeMap compared by time complexity, use cases, and interview patterns. Learn when O(log n) sorted access beats O(1) lookup.

Arrays give O(1) by position. Hash maps give O(1) by key. Learn the memory, cache, and time complexity tradeoffs and the coding interview mistake to avoid.

Stack vs queue explained: LIFO vs FIFO ordering, when to use each in coding interviews, BFS vs DFS, and the O(n) traps in Python, JS, and Java.