Big O Notation
What is Big O Notation?
A mathematical notation we use to describe the time complexity or space complexity of an algorithm. It provides a way to analyse and compare the efficiency of different algorithms by looking at how their performance scales with the input size.
In short, it's a reasonably straightforward way to analyse the efficiencies of algorithms, based purely on instruction sets.
The most general expression would be expressed as a function O(n) but let's look at more common expressions.
O(1) - Constant time
The algorithm's performance does not depend on the input size. It executes in a constant amount of time, regardless.
A simple example of this would be accessing an element in an array by index.
O(n) - Linear time
The algorithm's performance scales linearly with the input size.
As an example, iterating through the abovementioned array and performing a constant-time operation on each element.
O(n^2) - Quadratic time
Now the algorithm's performance is scaled directly proportional to the square root of the input size.
This often occurs in nested loops. Where each iteration contributes to the overall complexity of the algorithm.
O(log n) - Logarithmic time
With logarithmic time, the algorithm's time increases, but at a slower rate.
This graph uses considerably larger input sizes to better demonstrate the effect.
Now we're talking about algorithms that divide the problem space in half at each step. Think of something like a binary search.
O(n!) - Factorial time
We've hit the worst-case scenario where performance grows factorially with the input size.
The only example I can think of is iterating through an array and running a quadratic time algorithm on each element as well as all previous elements in the array (on every iteration).
How does Big O help us?
It's important to keep in mind that Big O described the upper bound (or worst-case scenario) of an algorithm's complexity. It's not designed to be a benchmarking tool, it wouldn't be effective at all, instead, it's a useful tool for comparing algorithms and making informed decisions about which one to use.
If you've never found yourself with multiple correct answers to a problem, not knowing which one would be better to implement, I envy you.