What is the time complexity of binary search on the answer, and why is it not O(log n)?
answer
- two factors, and they multiply
- one of them is the check's own cost
- the other counts halvings, not elements
- halvings depend on the span of values
- log of the value range, not log n
basics
~20 sBinary search on the answer costs O(check) x O(log R), where R is the span of candidate answer VALUES. The log factor comes from the value range, not the input size, and the feasibility check usually dominates.
solid answer
~50 sTotal cost is the cost of one feasibility check multiplied by the number of halvings, and the halvings are `log2(R)` where `R = hi - lo` measured in answer **values**. It is not `log n`, because the input size never determines the range. Take a transcoding farm: `n` clips of known duration arrive in a fixed queue order, each night processes the next contiguous stretch, and you want the smallest per-night minutes budget that clears everything in `d` nights. The range runs from the longest single clip up to the total duration `S`, and the check is one `O(n)` greedy sweep, so the total is `O(n log S)`. The check is where the real cost lives; the log factor is rarely more than a few dozen iterations, since even a range as wide as a fixed-width integer allows halves away in about 60 steps.
go deeper
Recall that the running time is two things multiplied: the cost of checking one candidate answer, and how many candidates the halving visits. Do not answer with a bare O(log n).
Explain precisely why the iteration count is the log of the span of answer values while the per-iteration cost is a full pass over the input, and give the combined bound for a concrete setup.
Demonstrate the engineering conclusion: the check runs dozens of times, so hoist any candidate-independent setup out of the loop and spend your effort on the check rather than on shrinking the range.
Own the numeric-safety and budget angle — a bound built from a sum or product can overflow a fixed-width accumulator, and a check with real side effects turns dozens of iterations into a cost the surrounding system has to absorb.
## Two independent factors Every binary search on the answer decomposes into exactly two costs that multiply: | Factor | What sets it | Typical value | |---|---|---| | Iterations | The span of candidate answer **values**, `R = hi - lo` | `log2(R)`, usually 20-60 | | Work per iteration | The feasibility check, which normally reads the whole input | `O(n)`, sometimes `O(n log n)` | Total cost is `O(check) x O(log R)`. Naming both factors out loud is the answer an interviewer is listening for; naming only one is the usual miss. ## The worked case A transcoding farm receives `n` clips with known durations `t[0..n-1]`. The queue order is fixed — clips must be processed in arrival order — and each night the farm takes the next contiguous stretch of the queue, up to a per-night budget of `B` minutes. No clip is split across nights. You have `d` nightly windows. Find the smallest `B` that clears the queue. The answer space is minutes of nightly budget. Its low end is the longest single clip (below that, one clip can never be scheduled at all) and its high end is `S = sum(t)`, which trivially clears everything in one night. Checking a candidate `B` is a single greedy pass: walk the queue, keep adding clips to tonight while they fit, open a new night when the next clip would overflow, and compare the night count to `d`. That is `O(n)` time and `O(1)` extra space. So: `O(n)` per check, `log2(S)` checks, total `O(n log S)`. ## Why `log S` is not `log n` This is the substitution people make without noticing, because ordinary binary search on a sorted array does `log2(n)` steps. Here `n` and the range are unrelated quantities. Three clips whose durations are in the millions give a tiny `n` and a large `log S`. A million clips of one minute each give a large `n` and a small `log S`. Doubling `n` doubles the check's cost — a **linear** hit on the total. Doubling the largest value adds exactly **one** iteration. That asymmetry is the practical takeaway: optimize the check, not the range. It also explains why an enormous answer range is not frightening. A range spanning what a fixed-width 64-bit integer can hold collapses in about 60 halvings. The value range is essentially a bit-width, and bit-widths are small. ## When the check is not O(n) The multiplication is honest only if you charge the check its true price. If a check sorts the input every time, it is `O(n log n)` per call and the total becomes `O(n log n log R)` — and the fix is usually to sort **once**, outside the loop, leaving an `O(n)` check inside. Hoisting invariant setup out of the search is the single biggest win available in this pattern. Conversely, if the check itself performs a nested scan and runs `O(n^2)`, the total is `O(n^2 log R)` and you should ask whether a different formulation exists before optimizing the loop. ## The hazard that bites in practice The upper bound is frequently a sum or a product of the inputs — `hi = sum(t)` here — and that quantity can be far larger than any single input. When durations are large and `n` is large, a fixed-width accumulator computing `hi` can overflow before the search even starts, and the search then runs against a nonsensical or negative bound. Two habits defuse it: compute the bound in a width that comfortably holds the worst-case total (or reason about the maximum before choosing one), and compute the midpoint as `lo + (hi - lo) / 2` rather than `(lo + hi) / 2`, since the naive form overflows whenever both bounds sit in the upper half of the representable range. The same care applies whenever the feasibility check multiplies a candidate answer by a count. ## Space The search itself is `O(1)`: two bounds and a midpoint. The space of the whole algorithm is whatever the check needs, which for a single greedy sweep is also `O(1)`. If you write the loop recursively, the recursion depth `log R` is stack space and belongs in the space bound — a small amount here, but it is not zero. ## Saying it well "One `O(n)` greedy pass per candidate, about `log2` of the total-duration range candidates, so `O(n log S)`; the range only ever contributes a few dozen iterations, so the check is where I would spend effort." That sentence carries both factors, their sizes, and the engineering conclusion.
- The upper bound is the sum of all clip durations. What can go wrong before the search even begins?A fixed-width accumulator can overflow while computing that sum, leaving `hi` wrong or negative and the search meaningless. Reason about the worst-case total up front and use a width that holds it. The related trap is the midpoint: compute `lo + (hi - lo) / 2`, because `(lo + hi) / 2` overflows whenever both bounds sit high in the representable range.
- Your feasibility check sorts the input on every call. How do you fix the complexity?Sort once, before the search, and let the check consume the sorted data. That turns `O(n log n) x O(log R)` into `O(n log n + n log R)`. Any setup that does not depend on the candidate answer should be hoisted out of the loop — the check is executed dozens of times, so per-call work is multiplied while one-time setup is merely added.
- Which hurts more: doubling the number of clips, or doubling the longest clip's duration?Doubling the clip count is far worse. It doubles the check's cost, and the check runs on every iteration, so the total roughly doubles. Doubling the largest duration doubles the value range, which adds exactly one halving — a single extra `O(n)` pass. This asymmetry is why tuning the check pays and shrinking the range rarely does.
saying these in an interview costs you the question
- Says O(log n) because the words binary search were used
- Leaves the feasibility check's cost out of the total
- Treats log of the value range as log of the input size
- Claims a huge value range makes the approach impractical
- Sorts inside the check instead of once before the search
- Computes the upper bound as a sum with no thought to overflow