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:
Recursion is used as a good way to keep the code easy to read and simple. But recursion has to be managed carefully to avoid creating inefficient algorithms.
We start off with a stop condition:
if ($input === 0 || $input === 0)
So if the input is 0 or 1, the function returns the input.
And if our input is not 0 or 1, we perform the function again twice. Once with the new input minus 1 (n-1). And another function call with the input minus by 2 (n-2).
It’s a small bit of code that cascades and continues to double until we have a 1 or a 0.
Let’s see a chart of how this works:
With the Fibonacci PHP function containing an input of four. We can see the amount of processing time doubles as we go down each level.
For every new input which does not meet the stop condition, we must run the function again twice.
This is okay for small input, but if this function becomes a core piece of code for your business, and is used to process a lot of data, watch out.
For example, if you have an exponential function that sends an email to all your members. As you get more members your application processing will dramatically increase.
Think about how the algorithm could scale.
Factorial Notation — O(!N)
Factorial notation is the least efficient of them all.
This is typically seen when an algorithm’s complexity size equals the input size multiplied by all the smaller numbers.
So what does that mean?
When you have an input of 5. The numbers that come before 5 are:
4, 3, 2 & 1
So a factorial complexity would produce the following with an input of 5:
5 x 4 x 3 x 2 x 1 = 120
If you had an input of 10 it would be:
10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 3,628,800
See how inefficient a factorial algorithm is as the input gets larger?
PHP Example
As with Exponential Notation, to get a Factorial Notation, doesn’t take a lot of code:
But this small segment of code has devastating effects.
This is another recursive function that stops when the input is 0. If the stop condition is not met, then a for loop occurs, looping through the size of the input. But with every loop of the input, the factorialNotation function is run.
Let’s see a chart of how this runs with an input of 3:
With an input of 3 we can see 6 final iterations of the factorial notation:
3 x 2 x 1 = 6
This is how we know an algorithm is factorial. When the final number of nodes equals the input multiplied by all the numbers that come before it.
General rules to remember for Big O Notation
There are a few rules you want to keep in mind when discovering the notation of an algorithm.
Drop the constants
When analyzing the code line by line, make sure to ignore the constants.
As the algorithm gets more complex, we know that constants stay the same, so there is no need to include them in the calculation.
This focuses our priority on the least efficient part of the code.
Ignore the smaller notations in an algorithm
When looking at the notation of an algorithm, the only concern is the least efficient notation.
Meaning more efficient notations can be ignored. Algorithms can become large, so we only need to concentrate on the least efficient part of the code.
You judge an algorithm by the least efficient area of code.
Understanding Big O Notation can help you become a better Software Engineer
By being able to identify notations, you will be able to assess your code and its impact on the system you are building.
A good rule of thumb when writing code, is to think of how the feature may be used in the future. If you are coding a feature to retrieve a data report of one client, this may not need to be efficient. But what if the spec changes down the line and you need to extend the code to produce a report of all your clients?
It’s always good to design for extendibility and that means coding efficient algorithms.
This will help you create features that are not resource intensive, and smash interviews when the inevitable Big O Notation question comes up.
