This page has focused on time complexity.
Let's now introduce ourselves to space complexity.
Space complexity compared to time complexity:
- Both assume that structure size (number of elements) grows towards infinity
- Time complexity assesses how hard an algorithm works (which impacts running time) relative to the structure growth
- Space complexity assesses how memory space used increases relative to the structure growth
Almost all data structures have a space complexity of O(n) as shown here.
Space complexity is a more important factor for linear searching algorithms (bubble sort, quick sort, merge sort, etc).