Available inEnglishFrenchGermanHindiPortugueseRussianSpanish
Big-O and Data Structures for Interviews
State the time and space cost of any operation on an array, linked list, hash map, tree, heap or trie, including the amortized case, and defend it out loud. For candidates preparing a coding interview or a data-structures final who know loops and hash maps but have only ever recognised a Big-O answer. Fifty-four cards in seven chapters; algorithmic patterns are covered by Coding Interview Patterns.
A program that costs n^2 takes 1 second on 1,000 items. Estimate its time on 2,000 items.
About 4 seconds
— Double the input, then square the doubling.
Source
Doubling n multiplies a quadratic cost by four, because (2n)^2 = 4n^2; ten times the input is a hundred times the work. This ratio trick answers 'and if the input grows?' without knowing a single constant: you never need the machine's speed, only the shape of the growth. Keep it beside its opposites: on an O(n log n) routine, doubling n a little more than doubles the time, and on O(log n) it adds one step.