mediumConceptScenarioMidSeniorStaff
A nightly job took 40 minutes last month and takes two hours forty on twice the data. What do you conclude about its complexity, and what would you measure next?
4 min readUpdated 2026-08-15Target archetype: Big Tech, Enterprise Captive, Product Startup
Answer
Short answer
A fourfold cost for a doubled input is consistent with quadratic growth, but two points fit infinitely many curves and a one-off cliff such as spilling out of memory produces the same ratio.
Use complexity analysis as the thread through the inferring complexity from two runtimes explanation: name the signal, then say what changes when it moves.
Was this answer helpful?
Likely follow-ups
- The ratios across four doublings come out as 2.1, 2.1, 2.1 and then 9. What single explanation fits all four?
- How would you bound the cost from the code when you cannot run it on production-sized data at all?
- The profile says 80 percent of the time is inside one library call. Does that change the asymptotic argument?
- The job is genuinely O of n log n and still too slow. What do you attack now?
Related questions
- The assistant wrote a working solution and the interviewer asks for its complexity and one input that breaks it. How do you verify code you did not write?mediumAlso on complexity-analysis and worst-case5 min
- How do you tell whether a value escapes to the heap, and how would you find the allocations that are costing you?hardAlso on profiling6 min
- A long-running Python service keeps climbing in memory and never comes back down. How do you work out where the memory went?hardAlso on profiling5 min
- How do you build a gold set for a retrieval system?mediumAlso on benchmarking5 min