Foundations 9 min read
Time and Space Complexity
Time complexity describes how the number of steps an algorithm takes grows as the input size n grows. Space complexity describes how much extra memory it needs as n grows. Both are written in Big-O notation, which keeps only the fastest-growing term.
Looking up a word: reading the dictionary page by page is O(n); opening it in the middle and halving each time is O(log n); knowing the exact page number is O(1).
Related topics