Member-only story
Big O Notation — How to Identify Exponential and Factorial Algorithms
If you were given a factorial Big O Notation Example, would you be able to identify it?
As a software engineer, you must be careful not to have an algorithm with the least efficient notations.
And to avoid writing these algorithms, you need to be able to identify them.
Here’s how to spot a Factorial and Exponential Algorithm with a Big O Notation Example
In previous articles, we have covered all the notations starting from the efficient range of notations: Constants and Linear.
To the less efficient range of notations known as N Log N, Quadratic and Cubic.
If you’re not sure where to start with the topic, check out: what is Big O Notation.
The graph above is a good way to picture Big O Notation complexity. This graph originates from the Big O Notation Cheat Sheet. Which is a great resource for discovering all the notations and specific algorithms that fall into each notation.
Looking at the chart, there are two notations pointing up vertically to the sky:
- Exponential Notation O(2^N)
- Factorial Notation O(!N)
These are notations you want to avoid at all costs.
Exponential — O(2^N)
Exponential is the second worst notation regarding efficiency.
This occurs when the amount of time/space complexity doubles as the input increases by 1.
It is best seen in a coding example using recursion, where the operation can get out of hand.
PHP Example
Let’s use the Fibonacci sequence to demonstrate exponential growth.
Now the code for this is simple, but the result is devastating for efficiency:
