Big O time complexities
Big O notation uses capital O to denote upper bound. It signifies that the actual running time could be less than but not greater than what the function expresses. It does not tell us the exact running time of an algorithm. Instead, it tells us how bad things could get as the input size grows large.
Imagine you have a messy room and need to find a specific sock. In the worst case, you have to check each item of clothing one by one (this is like a linear time algorithm). Big O tells you that even if your room gets super messy, you will not need to look at more items than are actually there. You might get lucky and find the sock quickly! The actual time might be much less than the Big O prediction.
When analyzing algorithms, the following classifications of time and space complexities are most encountered:
Notation | Name | Explanation |
O(1) | Constant | The algorithm's runtime or space usage remains the same regardless of the input size (n). |
O(log(n)) | Logarithmic... |