Big O examples
We will try to determine Big O for different snippets of code exactly as you will see at interviews, and we will go through several relevant lessons that need to be learned. In other words, let's adopt a learning-by-example approach.
The first six examples will highlight the fundamental rules of Big O, listed as follows:
- Drop constants
- Drop non-dominant terms
- Different input means different variables
- Different steps are summed or multiplied
Let us begin with trying out the examples.
Example 1 – O(1)
Consider the following three snippets of code and compute Big O for each of them:
// snippet 1 return 23;
Since this code returns a constant, Big O is O(1). Regardless of what the rest of the code does, this line of code will execute at a constant rate:
// snippet 2 - 'cars' is an array int thirdCar = cars[3];
Accessing an array by index is accomplished with O(1). Regardless of how many elements are...