Why can't O(E+S) over E events and S servers be simplified to O(E)?
answer
- how many independent input axes are there
- dropping terms needs one variable, not two
- could S ever outgrow E
- sequential scans add, nested scans multiply
- collapse is valid only under a stated relation
basics
~20 sE and S are independent inputs, so neither provably dominates the other. Lower-order terms may only be dropped within a single variable. O(E+S) becomes O(E) only when the problem guarantees S is bounded by a multiple of E.
solid answer
~40 sDropping a term is legitimate only when one term provably dominates the other for all large inputs, and that requires both to be functions of the same variable. `E` and `S` are free and independent: nothing in the problem prevents a fleet of `S` servers from outnumbering the `E` events seen in a quiet window, so neither term dominates across the whole input space. The two bounds also describe different code: `O(E+S)` is two sequential scans, `O(E*S)` is a nested scan, and at `E = 2x10^6` and `S = 4x10^3` that is roughly two million steps versus eight billion. The collapse to `O(E)` is honest only under a stated relation — for instance, if every server contributes at least one event then `S <= E`, and only then does `O(E+S) = O(E)`.
code
pseudocode · 11 lines// shape A: two sequential scans -> O(E + S)
for i in 0..E-1:
record(events[i])
for j in 0..S-1:
flush(servers[j])
// shape B: nested scans -> O(E * S)
for i in 0..E-1:
for j in 0..S-1:
if owner(events[i]) == servers[j]:
attribute(events[i], servers[j])go deeper
Know that a plus sign and a times sign in a bound describe different code: work done one after another adds, work nested inside other work multiplies. Be able to read a two-loop fragment and say which one it is.
Explain why dropping a term requires both terms to live on the same input axis, and give the condition under which the collapse becomes legal. An interviewer wants the reasoning, not the rule recited.
Demonstrate that you state the assumption a simplification rests on, because that assumption is what breaks in production when a fleet grows or an upstream starts batching differently. Name the regime alongside the bound.
Own the habit of writing bounds that survive a change in the operating point. When two teams report costs in different variables, you are the one who makes the units comparable before a capacity decision is made on them.
## Two different simplification rules, often confused When a cost is `3n^2 + 50n + 900`, dropping everything but `n^2` is sound: all three terms are functions of the same variable, and for large enough `n` the quadratic term exceeds the others by any margin you like. There is a *single* input axis, so "eventually largest" is a well-defined idea. When a cost is `E + S`, there is no single axis. `E` and `S` are independent coordinates of the input, and the input space is the whole plane of pairs. To claim `E + S` is `O(E)` you must show there is a constant `c` with `E + S <= c*E` for all sufficiently large inputs — which fails the moment `S` is allowed to grow while `E` stays small. A monitoring job that scans a fleet of 4,000 servers during a minute with 12 events is a real point in that space, and there `S` is the whole cost. The misconception this question targets is treating `S` as a "lower-order term" because it happens to be the smaller number in today's data. Current data is one point; an asymptotic claim quantifies over all of them. ## Addition versus multiplication The distinction between `O(E+S)` and `O(E*S)` is not notation pedantry — it is the difference between two shapes of code, and at realistic sizes the two answers differ by orders of magnitude. | bound | code shape | steps at E=2x10^6, S=4x10^3 | |---|---|---| | O(E+S) | one scan over events, then one scan over servers | about 2.0x10^6 | | O(E log S) | one lookup per event into a structure holding the servers | about 2.4x10^7 | | O(E*S) | for every event, a scan over every server | 8x10^9 | Sequential work adds; nested work multiplies. When someone reports a bound, the fastest way to sanity-check it is to ask which loops are inside which. ## When a collapse is legitimate Multi-variable bounds *can* be simplified, but only against a stated relation between the variables: - **A domain guarantee.** If the `E` events are the events emitted by those `S` servers and each server emits at least one, then `S <= E`, hence `E + S <= 2E` and `O(E+S) = O(E)` honestly. - **A bounded variable.** If `S` is capped by configuration at, say, 64, it is a constant and disappears — but write down the assumption, because a cap that later becomes a knob silently invalidates the bound. - **A regime you name.** You may say "in the regime `S << E` this behaves as `O(E)`", which is a claim about an operating point rather than about the algorithm, and it should be stated as such. What you may never do is drop a variable because it is currently smaller. That is an empirical observation being smuggled in as an asymptotic proof. ## Comparing mixed multi-variable bounds Once both variables are in play, comparison requires care: `O(E+S)` beats `O(E log S)` when `S` is modest, but if `S` dwarfs `E` — a huge fleet, a trickle of events — then `E + S` is essentially `S` while `E log S` stays small, and the ranking flips. There is no total order over multi-variable bounds; there is a ranking *per region* of the input space. The professional habit is to state the region you care about along with the bound: "`O(E log S)`, and we operate with `E` in the millions and `S` in the low thousands". ## How to present one in an interview Say which variables you are counting and what they count, derive the bound from the loop structure, then name the regime. "Each of the `E` events does one lookup against a structure over `S` servers, so `O(E log S)` time and `O(S)` space; with `S` in the thousands the log factor is about 12, which is why this beats the nested version by three orders of magnitude." That answer is checkable, and it shows the thing the question is really probing: that you know which simplifications are theorems and which are assumptions about your data.
- What relation would make the collapse to O(E) legitimate here?Any guarantee that `S` is bounded by a constant multiple of `E`. The natural one in this setting: if every one of the `S` servers contributes at least one of the `E` events, then `S <= E`, so `E + S <= 2E` and the bound is genuinely `O(E)`. A configuration cap on `S` works too, since a bounded variable is a constant. State whichever assumption you are leaning on, because it is the thing that breaks first.
- Where does an O(E log S) bound sit relative to the other two?Between them, and not always in the same place. With `E = 2x10^6` and `S = 4x10^3`, `log2 S` is about 12, so `E log S` is about `2.4x10^7` — twelve times the cost of `E + S` but 300 times cheaper than `E * S`. If the fleet grows until `S` dwarfs `E`, however, `E + S` is dominated by `S` and can exceed `E log S`. Multi-variable bounds rank per regime, not globally.
- A routine scans all E events once, then for each server scans all E events again. What is the bound?`O(E + S*E)`, which simplifies to `O(S*E)` — here the two terms *are* comparable, because `S*E >= E` for `S >= 1`, so the standalone `E` is genuinely lower-order. This is the case where dropping is a theorem rather than an assumption: the dropped term is dominated over the entire input space, not merely at today's sizes.
Merging two guest lists costs the sum of their lengths; introducing everyone on one list to everyone on the other costs the product. Nobody can tell you which list is longer in advance.
saying these in an interview costs you the question
- Just drop the smaller variable like a lower-order term
- O(E+S) and O(E*S) are basically the same thing
- S is always tiny in practice so it vanishes
- With two variables you report whichever is bigger
- Multi-variable bounds can never be simplified at all