One of the wonderful things about coding is that there are usually a multitude of ways to solve any single problem. However, could there be a right or wrong way to code an algorithm as long as the result is giving you the desired output?
In reality, there are definitely better ways of solving problems.
So what does better really mean? Better means more efficient.
But given two algorithms, how do you measure better? A very simple approach could be measuring the seconds it takes to finish executing.
This approach presents with a problem - if I measure the time it take on my computer, and then let's say you run that same algorithm and measure the time on your computer, it will actually vary in time! Not only will different machines record different times, the same machine will record different times as well! This isn't a very reliable method of comparison - especially since for some very fast algorithms, speed may not be precise enough.
Instead of measuring seconds, we can measure the number of simple operations the computer has to perform.
How do we do that?
Big O is a way we can describe algorithms and compare them relatively.
The most simple explanation I've heard is this:
Big O allows us to talk about how the runtime of an algorithm grows as the inputs grow. In other words, we can compare the relative growth rates of different algorithms.
Common rates of increase are depicted in the graph below:
Examining this graph, we can see that the best rate of increase is no increase at all - O(1). Ha! Wonderful.
This isn't always practical so we can use this graph as a visual of how the other rates compare. Given O(n) and O(n²) for example - as the number of inputs increase, O(n) increases linearly while O(n²) increases quadratically! Yikes!
3 Helpful Rules to Remember
1. Constants don't matter, drop them.
O(5n) --> O(n)
O(15) --> O(1)
O(5n²) --> O(n²)
2. Smaller terms don't matter. Drop them.
O(n + 5) --> O(n)
O(10n + 25) --> O(n)
O(5n² + 3n + 2) --> O(n²)
3. Two loops is always better then a nested loop.
A good easy rule to follow when seeing a nested loop is to multiple by the number of nested loops to give you the Big O.
For the below example of a simple nested loop, the Big O would be n * n = O(n²)
While for two individual loops - Big O is O(n)
Happy Coding,
Michaella
Note: I've been using Big O in talking about time complexity - but there is also space complexity (how much memory we need in order to run an algorithm) which we can use Big O to compare as well. This is a different topic which I did not go into, but I highly encourage you to read about it as for the same algorithm, you can have different Big O's for time and space complexity!
Top comments (0)