This post gonna focus on theory only, no practicing here. We will go through the examples and practice analyzing big O notation in part 2.
I. What is Big O
Imagine we have multiple implementations of the same method/function, how can we determine which solution is the best? There must be a method to calculate, to measure those solutions and big O is the result for us to look at.
Actually, there are always trade-offs between approaches, the important thing is to have a precise vocabulary to discuss those approaches, and consider which one should be applied to the case.
II. Time Complexity
Of course, time matters. A few things we should focus on when discussing an implementation:
- Time, which one is faster?
- Less memory-intensive? (space complexity – we will discuss this later)
- More readable
Time should be the first thing we focus in my opinion. Actually, I do see a lot of cases in real life where people accept the memory intensive, to have better optimization of time when building APIs.
And we can not just execute the implementations and compare the time we got on our machine!
III. Big O expressions
Some rules when calculating big O:
- Constants don’t matter, for example
- O(2n) => O(n)
- O(50) => O(1)
- O(3n^2) => O(n^2)
- Smaller terms don’t matter
- O(n^3+10n+100) => O(n^3)
- O(n^2+5n) => O(n^2)
- And to be clear:
- Variable assignment is constant
- Arithmetic operations are constant
- Accessing elements in an array or object is constant
- In a loop, the complexity is the length of the loop times the complexity of what happens in the loop
- Big O Notation doesn’t care about precision, only about general trends (linear, quadratic, constant)
One more type of big O is logarithm complexity. Some searching, sorting (time) and recursion (space) algorithms have logarithmic time complexity
IV. Space Complexity
To be clear, the space we are talking about here is the Auxiliary space, which is the space required by the algorithm, not including the space taken up by the input.
And yes, we can also use big O notation to analyze space complexity and to consider how much memory we need to allocate in order to run the method.
Some basic rules:
- Most primitives (booleans, numbers, null…) are constant space
- Strings which has a length equal to n will require O(n) space
- Same for Array, space required is O(n)
V. Conclusion
This is just the warm-up, in part 2, we will go through examples and practice analyzing the big O Notation