Big-O as an Interview Time Budget

The 16-Minute App

An app holds a million items and answers a million lookups. Each lookup scans every item.

That is 10^12 inspections. At about 10^9 simple operations per second, the job takes 1000 seconds, roughly 16 minutes and 40 seconds.[[2]](https://opendatastructures.org/ods-python/1_1_Need_Efficiency.html)

Switch to binary search, and each lookup needs about 20 steps instead of about a million.[[3]](https://cp-algorithms.com/num_methods/binary_search.html)

The whole job drops to about 2·10^7 steps, well under a second. The machine stayed the same. Only the method changed.

Method Beats Machine

Sorting a million numbers shows the same gap.

Quicksort needs about 20,000,000 steps on average. Bubble sort needs about 1,000,000,000,000.[[1]](https://xlinux.nist.gov/dads/HTML/bigOnotation.html)

In 1984, Jon Bentley showed a microcomputer running BASIC beating a supercomputer running FORTRAN.[[1]](https://xlinux.nist.gov/dads/HTML/bigOnotation.html) The slower machine had the better algorithm.

Good structure also scales. A sorted structure can hold a billion items while inspecting at most 60 items during any operation.[[2]](https://opendatastructures.org/ods-python/1_1_Need_Efficiency.html)

What Big-O Actually Says

Take n² + 3n + 4. For every n above 10, it stays below 2n².[[1]](https://xlinux.nist.gov/dads/HTML/bigOnotation.html)

That is the definition. f(n) = O(g(n)) when some constant c and starting point k give f(n) ≤ c·g(n) for all n ≥ k.[[1]](https://xlinux.nist.gov/dads/HTML/bigOnotation.html) Neither c nor k may depend on n.

So constant factors and lower-order terms drop out. n² + 3n + 4 is O(n²).

A fixed number of passes also drops out. Scanning an array three times is still O(n).[[5]](https://www.techinterviewhandbook.org/algorithms/array/)

The Tightest Bound Wins

Is 103n + 7 O(n²)? Technically, yes.

Big-O is only an upper bound, so anything O(n) is also O(n²) and O(n³). Those answers are true but loose.

Interviewers expect the tightest simple bound: O(n). Reading O as exact equality is a misuse. The exact growth rate has its own name, Θ.[[1]](https://xlinux.nist.gov/dads/HTML/bigOnotation.html)

A related trap: two passes over an array do not make code O(n²). They make it about 2n steps, which is O(n).[[5]](https://www.techinterviewhandbook.org/algorithms/array/)

Plug In the Input Limit

Before you code, put the input limit into your bound.

With 10^6 items, an O(n²) method takes 10^12 steps, about 16 minutes.[[2]](https://opendatastructures.org/ods-python/1_1_Need_Efficiency.html) An O(n log n) method takes about 2·10^7 steps.[[1]](https://xlinux.nist.gov/dads/HTML/bigOnotation.html)

Range-sum queries: Q queries over N numbers, both up to 10^5, cost O(NQ) if answered naively. That is about 10^10 steps, which will almost certainly exceed the time limit.

Prefix sums make each query constant time. Treat 10^9 operations per second as a rough rule of thumb, not a fixed limit.

The Floor: BTTC

Can you sum an array faster than O(n)? No. Every value must be read.

Tech Interview Handbook calls this the best theoretical time complexity (BTTC), the bound no solution can beat.[[4]](https://www.techinterviewhandbook.org/coding-interview-techniques/) Reading the input usually sets it.

Counting islands in an n by m grid is O(nm), because any cell might be land.[[4]](https://www.techinterviewhandbook.org/coding-interview-techniques/) A 1000 by 1000 grid means 10^6 cell visits.

Input facts can lower the floor. In a sorted array, finding a value is O(log n), and finding the largest is O(1) because it is the last element.[[4]](https://www.techinterviewhandbook.org/coding-interview-techniques/)

Already at the Floor?

Your array sum is O(n). The interviewer asks for something faster. What now?

Once a solution meets the BTTC, a lower Big-O is impossible. Faster usually means fewer passes or less extra memory.

Time usually comes first: "Most of the time, time complexity is more important than space complexity."[[4]](https://www.techinterviewhandbook.org/coding-interview-techniques/)

Big-O also hides constants. Two O(n) solutions can differ several times in real speed, and a simple quadratic loop may be fine on tiny inputs.

Is O(n²) a technically valid Big-O description for an algorithm that runs in O(n)?

• Yes, but it is a loose bound
• No, because Big-O must state exact growth

Answer: Yes, but it is a loose bound

Yes. Big-O gives an upper bound, so an O(n) function is also O(n²) and O(n³). However, interviewers expect the tightest simple bound, which is O(n).

For these two array tasks, summing every value has BTTC _____, while finding the largest value in a sorted array has BTTC _____.

Answer: For these two array tasks, summing every value has BTTC O(n), while finding the largest value in a sorted array has BTTC O(1).

Summing requires reading every array value, so its best possible time is O(n). In a sorted array, the largest value is already at the last position, so it can be accessed in O(1) time.

What is the tightest simple Big-O bound for an algorithm with step count n² + 3n + 4?

• O(n)
• O(n²)
• O(n³)
• O(1)

Answer: O(n²)

The n² term grows fastest. The constant multiplier, the lower-order 3n term, and the constant 4 do not change the asymptotic class, so the expected answer is O(n²).