Complexity Analysis

Doubling makes each resize twice as rare as the last, so the copies across n appends sum to 1+2+4+...+n, which stays under 2n. That is O(n) total work spread over n appends, hence O(1) per append on average over the sequence.

Target O(n log n) or better. Quadratic work at n = 100,000 is about 10^10 operations, far past the rough budget of 10^8 simple operations per second, while n log n lands near 1.7 million — comfortably inside it.

Each membership check scans everything kept so far, so the check at step k costs O(k), not O(1). Summing 1 through n gives O(n^2). A hash-based set makes each check expected O(1), so the whole pass becomes O(n).

Loops side by side add their trip counts: n + n = 2n, and constants drop, so it stays O(n). Nesting multiplies instead: the inner loop restarts in full for every outer step, giving n * n = O(n^2).

Saying an algorithm is O(n) claims its running time is bounded above by a constant times n for all sufficiently large inputs. Constants and lower-order terms are dropped because the notation describes growth rate, not exact operation counts.

O(1) describes only the best case, where the repeat appears immediately. An early-exit duplicate scan is O(n): a batch with no repeats forces reading every record, and that worst case is what you report.

At a billion events an O(n log n) pass takes roughly 3x10^10 steps, which is seconds. An O(n^2) pass takes 10^18 steps, about thirty years at a billion steps per second. The gap grows with n, so faster hardware never closes it.

The bound binds a model, not the task. It covers only algorithms that learn order by comparing pairs of keys. Sorts that use a key's value directly as a position escape it and run in linear time.

Each call spawns 4 children, so counts multiply level by level instead of adding. Depth d holds 4^d live calls, and L levels of multiplying give 4^L complete patterns. Branching compounds; it does not accumulate.

T(n) = T(n/2) + O(1) solves to Θ(log n). Each call spawns one subproblem of half the size and does constant work, so the total is the number of halvings that fit in n, not n itself.

Halving only sets the number of levels, about log n; the work per level decides the rest. T(n)=T(n/2)+O(1) does O(1) per level, so O(log n). T(n)=2T(n/2)+O(n) does O(n) per level, so O(n log n).

Auxiliary space counts only the extra memory an algorithm allocates while it runs; total space also counts the input it was handed. A scan that keeps two counters over a million-element input is O(1) auxiliary but O(n) total.

Every unfinished recursive call keeps a frame on the call stack holding its arguments, locals and return address. That memory is real, so a recursion nesting d levels deep costs O(d) space even when it allocates nothing itself.

Bound the total work, not the worst inner-loop length. Each token is pushed at most once and popped at most once, so every inner-loop iteration across the entire scan is charged to a distinct pop — at most n of them overall.

Every iteration pays for the sort, so n rows over m transactions cost O(n · m log m). The sort's input never changes here, so hoisting it above the loop drops the job to O(m log m + n).

Starting the inner loop at i+1 checks each unordered pair once instead of twice, so the body runs n(n-1)/2 times rather than n^2. That halves the work, but half of a quadratic is still quadratic.

Technically true, practically misleading. Big-O is only an upper bound, so a linear scan is O(n^2) in the same trivial sense it is O(n^3). The implied complaint — quadratic growth — is false: the tight bound is Theta(n).

A first-element pivot on sorted data is the smallest element in its range, so each partition splits off one element. The recursion runs n levels deep with linear work per level: O(n^2). Tidy input, maximally unbalanced splits.

The call count grows like 1.618^n — exponential, not linear. Although only n+1 distinct arguments exist, the naive version remembers nothing, so the same argument is recomputed from scratch across many branches of a two-way call tree.

The first is case 3: watershed n^(log_2 2) = n loses to f(n) = n^2, so the root dominates. The second is case 1: watershed n^(log_2 4) = n^2 beats f(n) = n, so the leaves do. Both give Θ(n^2).

Four-way branching is cancelled by quarter-sized subproblems: level i holds 4^i calls on inputs of size n/4^i, so each level still does about n work. With about log base 4 of n levels, the total is O(n log n).

More is required. In-place means O(1) auxiliary space — a constant amount of scratch memory, not zero. A routine that allocates a full-size temporary and copies it back over the caller's buffer is destructive, not in-place.

O(h), where h is the tree's height: only the current root-to-node path is in progress at once. A height-balanced tree gives O(log n); a degenerate tree that is one long chain gives O(n).

Bit i flips only once every 2^i increments, so n increments cost at most n + n/2 + n/4 + ... < 2n flips. That is O(1) amortized per increment, even though one carry chain can flip every bit.

A fixed step makes resizes fire at a constant rate forever while each copies more elements, so copy sizes form the arithmetic series 1000+2000+...+n. That sums to about n squared over 2000, and per-append cost grows with n.

Because the table's capacity grows multiplicatively, so full rebuilds become exponentially rarer as they get more expensive. The rebuild work across n inserts sums to a geometric series bounded by O(n), the same argument that makes buffer append amortized constant.

Because the cost is 2^n times n, not 2^n alone. At n = 18 that is about 4.7 million operations; at n = 25 it is roughly 840 million — nearly an order of magnitude past a one-second budget.

A bounded value range is a second constraint axis: with only 1,440 distinct values you can tally occurrences per value instead of comparing elements, costing about O(n + k) time and O(k) space rather than n log n.

Each level divides the width rather than subtracting from it, so the width reaches one after about log2(n) halvings, where n is the starting width. Repeated division gives a logarithmic count; repeated subtraction is what would give a linear one.