Comparison

If `O(n)` is the worst-case ceiling on an algorithm's running time, what tells you the floor, the absolute minimum work the algorithm must always do? That is the question **Big-Omega Notation** answers, and it is the second pillar of asymptotic analysis that turns half a description of performance into the full picture. This lesson introduces `Omega(g(n))` as a formal lower bound, with the mirror-image definition of Big-O: there exist positive constants `c` and `n0` such that `f(n) >= c * g(n)` for all `n >= n0`. You will practice proving Omega claims, analyze the best-case behavior of familiar algorithms (linear search, bubble sort, insertion sort), and meet a famous problem lower bound: any comparison-based sort must do at least `Omega(n log n)` comparisons in the worst case. You will also learn to spot when an algorithm is asymptotically optimal because its upper and lower bounds coincide. This lesson builds directly on **Big-O Notation (Upper Bound)**, where you learned to express upper bounds on growth using constants `c` and `n0`. Big-Omega flips the inequality from `<=` to `>=` and reuses the same machinery to describe floors instead of ceilings. Once you are comfortable bracketing algorithms with both bounds, you will be ready for **Big-Theta Notation (Tight Bound)**, where the upper and lower bounds meet to give the most precise complexity statement possible.

When you can say *both* that an algorithm runs in `O(n log n)` and that it must do at least `Omega(n log n)` work, the ceiling and floor have collapsed onto the same growth rate. That coincidence is the most informative complexity statement you can make, and it is what **Big-Theta Notation** captures in a single symbol. This lesson defines `Theta(g(n))` as the intersection of Big-O and Big-Omega: there exist positive constants `c1`, `c2`, and `n0` such that `c1 * g(n) <= f(n) <= c2 * g(n)` for all `n >= n0`, the so-called sandwich property. You will practice classifying functions and algorithms by their tight bound, learn when Big-Theta is appropriate (best and worst case have the same growth rate) versus when only Big-O is honest (the cases differ), and see why merge sort is `Theta(n log n)` while linear search is *not* Theta of any single function. This lesson stitches together two ideas you have already met. From **Big-O Notation (Upper Bound)** you have the ceiling `f(n) <= c * g(n)`, and from **Big-Omega Notation (Lower Bound)** you have the floor `f(n) >= c * g(n)`. Big-Theta simply requires both bounds to hold for the same `g(n)`, so an algorithm only earns a Theta label when its upper and lower bounds genuinely match. With all three asymptotic notations in hand, you will be ready to switch focus to **Memory Models**, where the same growth-rate thinking gets applied to space rather than time.

When a paper claims an algorithm runs in `O(n^2)`, that statement leaves a question wide open: does the algorithm *actually* take quadratic time, or could the bound be loose? **Little-o** and **little-omega** are the notations that close that gap. `f(n) = o(g(n))` says `f` grows *strictly* slower than `g`, never matching its rate, and `f(n) = omega(g(n))` says `f` grows strictly faster. They are the precision tools of theoretical CS. This lesson defines both notations using the formal limit-based criterion: `f(n) = o(g(n))` iff `lim f(n)/g(n) = 0`, and `f(n) = omega(g(n))` iff `lim f(n)/g(n) = infinity`. You will prove and disprove `o` and `omega` claims for common function pairs (`n` vs `n^2`, `log n` vs `n`, `n` vs `n log n`, `2^n` vs `n^k`), use these notations to rank growth rates strictly, and see how the full five-notation system fits together: `O` and `Omega` allow equality, `Theta` requires it, while `o` and `omega` forbid it. This lesson builds on three earlier asymptotic foundations. From **Big-O Notation (Upper Bound)** you have non-strict ceilings; from **Big-Omega Notation (Lower Bound)** you have non-strict floors; and from **Big-Theta Notation (Tight Bound)** you have the exact-rate case. Little-o and little-omega simply require the inequality to be strict, ruling out the matching case that Big-O and Big-Omega permit. With all five notations under your belt, you will be ready for **Complexity Classes (Conceptual Overview)**, where these comparisons get used to separate classes like `P` and `NP`.

A modern hard drive reads about 100 MB per second sequentially, but a single random seek still costs around 10 milliseconds; that gap is roughly seven orders of magnitude. A binary tree of a billion keys has 30 levels, which means 30 random seeks per lookup. **B-Trees and B+ Trees** keep each node fat enough to fill a disk page, branch into hundreds of children, and answer the same lookup in three or four seeks. That is why every relational database you have used relies on this family for its indexes. This lesson covers the B-Tree minimum-degree parameter `t` and the resulting key-and-child counts at every node, the proactive split during insert that keeps the height bounded by `O(log_t n)`, the merge-or-redistribute logic for delete, and the B+ Tree refinement that pushes all data to the leaf level and links those leaves together so range queries become a sequential scan after a single descent. In **Binary Search Tree (BST)**, every node held a single key and at most two children; that geometry is fine for memory but disastrous for disk because each comparison forces a separate I/O. B-Trees flip the design: keep every node wide so a single I/O resolves many comparisons at once. Next, **Splay Tree** explores a third self-balancing strategy in which the tree reshapes itself around access patterns rather than maintaining strict structural invariants.

Insert the keys 1, 2, 3, 4, 5 into a plain BST in that order and you do not get a tree at all; you get a right-leaning chain with `O(n)` search. The fix is to detect imbalance after every insert or delete and rotate the offending subtree back into shape, which is exactly what a **Balanced BST** does. AVL and Red-Black trees are the two most influential designs in this family. This lesson covers the balance factor (height of left subtree minus height of right subtree), AVL's strict `|bf| <= 1` invariant enforced by the four rotation cases (LL, RR, LR, RL), and Red-Black trees' five color and structural invariants enforced by recoloring plus rotations. You will trace insertions through both schemes, see why Red-Black trees do fewer rotations on average and so are preferred by C++ `std::map` and Java `TreeMap`, and analyze the height bound (`<= 2 log n`) that gives both their worst-case `O(log n)` guarantee. In **Binary Search Tree (BST)**, you implemented search, insert, and delete that respected the ordering invariant but said nothing about shape; the resulting `O(n)` worst case is precisely what self-balancing solves by maintaining a height invariant in addition to the ordering invariant. Next, **B-Trees and B+ Trees** generalize the same balanced-tree idea to nodes that hold many keys at once, an essential design choice for disk-resident data.

An operating system rotating turns among four CPU-bound processes, a music player on shuffle-repeat, and the classic Josephus problem all share the same shape: a finite list of items consulted in cyclical order, where 'after the last' means 'back to the first'. A **Circular Linked List** encodes that shape directly, with the last node's `next` pointer wired to the head instead of `null`. This lesson covers the circular singly linked list and its doubly linked variant, the stop condition for traversal (return to the starting node rather than waiting for `null`), insertion at the head and at the tail in `O(1)` when a tail pointer is maintained, and deletion that correctly handles the wrap-around. You will also compare circular structures with the standard linear forms so you know when bending the list back on itself is the right call and when it just complicates traversal. In **Linked Lists (Singly)**, traversal terminated when you reached a `null` next pointer; here, the same loop must compare against the starting node instead, a small change that exposes the distinction between cycle detection and cycle definition (Floyd's tortoise-and-hare reuses this idea later). With all three linked-list shapes covered, the curriculum next pivots to tree-based and array-based structures with stronger time guarantees.

Deleting a node from a singly linked list when you only hold a pointer to that node is genuinely awkward: you need the previous node too, and finding it is `O(n)`. Add a `prev` pointer to every node and the same delete becomes four pointer rewires in `O(1)`, which is exactly the upgrade that powers LRU caches and the browser back-forward stack. This lesson covers the **Doubly Linked List** node layout (`value`, `next`, `prev`), bidirectional traversal, insertion at head and tail and after a given node, deletion by node reference and by value, and the sentinel (dummy head and tail) pattern that eliminates almost all null-check edge cases in pointer-heavy code. You will also weigh the per-node memory cost of the extra pointer against the operations it unlocks. In **Linked Lists (Singly)**, head insertion was already `O(1)` but mid-list deletion required carrying a trailing pointer during traversal. The doubly linked list removes that constraint: every node knows its predecessor, so you can splice it out without any extra bookkeeping. Next, **Circular Linked List** keeps a single direction of links but bends the list back on itself, which turns out to be the right shape for round-robin scheduling and circular buffers.

Drop a million IDs into a `Set`, ask `set.has(id)` for any one of them, and the answer comes back in expected constant time without any ordering, sorting, or scanning. That single primitive (membership testing) is what makes a **Set** the quiet workhorse behind deduplication, visited-node tracking in graph traversal, and almost every cache-invalidation routine you will read. This lesson covers the uniqueness invariant of a set, the four core operations `add`, `delete`, `has`, and iteration in both JavaScript's `Set` and Python's `set`, and the four classical set-theory operations: union, intersection, difference, and symmetric difference. You will see why a set is implemented as a hash map whose values are unused, and you will practice the visited-set pattern that reappears in BFS, DFS, and cycle detection. In **Hash Map (Dictionary) Basics**, you learned that a hash function maps keys to bucket indices for `O(1)` get and set. A set keeps only the keys, drops the values, and exposes the resulting structure as a pure membership data type. Next, **Trees: Binary Tree Fundamentals** moves from flat unordered collections to hierarchical structures, where parent and child relationships unlock entirely new traversal patterns.

Redis backs its sorted sets with one. LevelDB and RocksDB use one for their in-memory memtables. Java ships a `ConcurrentSkipListMap` in its standard library because lock-free skip lists are dramatically easier to implement than lock-free balanced BSTs. The structure those production systems share is a **Skip List**: a sorted linked list with a few extra express-lane pointers that turn `O(n)` search into `O(log n)` expected. This lesson covers the multi-level structure (a base list with every element, plus higher levels each containing a random subset that acts as a fast-path index), the coin-flip promotion rule that decides how many levels each new node spans, and search, insert, and delete operations whose expected cost is logarithmic without any tree rotations or balance bookkeeping. You will trace the search path that drops one level at a time whenever the next pointer overshoots the target, and you will analyze why a fair coin produces the right level distribution. In **Linked Lists (Singly)**, a search was `O(n)` because the list offered exactly one pointer per node. A skip list keeps that simple node, just adds a small array of forward pointers to higher levels, and lets randomness substitute for the deterministic balancing that AVL and Red-Black trees rely on. Next, **Balanced BST (AVL / Red-Black)** is the deterministic counterpart: same logarithmic guarantees, fundamentally different implementation strategy.

Boyer-Moore is the algorithm `grep` actually uses, and it has a counterintuitive property: longer patterns make it _faster_, not slower, because the bad-character rule lets it skip whole chunks of the text without inspecting them. The best case is `O(n / m)`, sublinear in the text length. The same insight (start from the right, jump aggressively on mismatch) defines a different family of pattern-matching algorithms from the linear-scan family of KMP and Z. **Pattern Matching Algorithms** rounds out the string-search toolkit. You will implement Boyer-Moore with both the bad-character rule and the good-suffix rule, build a deterministic finite automaton (DFA) from a pattern and use the resulting state-transition table for `O(n)` matching after `O(m * |alphabet|)` preprocessing, and extend pattern search into two dimensions row by row. The lesson closes with a head-to-head comparison of every string-matching algorithm you have seen so far (KMP, Z, Rabin-Karp, Manacher, Aho-Corasick, Boyer-Moore, DFA), so you can pick the right tool for any matching task: long patterns, multi-pattern, streaming, or 2D. In **String Algorithms**, you mastered the failure-function family of linear-time matchers. This lesson adds the right-to-left family and the automaton-construction family. From here, **Advanced Greedy & Data Structures** turns to monotonic stacks.