As a Software Engineer, you are guaranteed to get a question about Big O Notation in a tech interview.
But what is Big O Notation? And why do you need to know about it?
What is Big O Notation?
Big O notation is a way to define how an algorithm grows in size as the input size grows.
The notation involves using a label (known as a growth hierarchy), to rank how efficient the algorithm is in time and space.
That sounds complex so I will break this down into a real-life example.
Let’s use a restaurant as an example
John and Max are meeting for dinner on Friday evening, the busiest time of the week for restaurants.
They both need to be finished within ninety minutes and are deciding between two restaurants.
But how will they decide which one is the fastest option? and how can they be sure the restaurant will not take too long during the busiest time of the week?
If we compare the technical definition of Big O. In this example, the restaurant is the algorithm, and the input is the number of customers.
The number of customers is something that changes based on demand, and we need to understand how the restaurant deals with the input at high capacity.
As the number of customers within the restaurant grows, so does the time it takes for each customer to be served their meal.
But not every restaurant handles a large number of customers the same way.
Let’s look at both restaurants:
Restaurant 1 – A la Carte restaurant:
- A server takes the customer’s order and a chef will prepare the order on demand.
- There is only one chef who cooks every meal.
- The restaurant is small with 4 tables.
Restaurant 2 – Buffet:
- Once guests have paid, they can start serving themselves pre-prepared food.
- The buffet contains multiple dishes and many chefs who continue to refill the food.
- The restaurant is large with 30 tables.
John and Max can guess which restaurant will be the fastest option, but they need to know for sure.
Measuring the efficiency of each restaurant using time and space complexity.
When assessing which restaurant is the fastest, there are two factors:
- Time Complexity – How much time it takes for each customer to enter and leave the restaurant as the number of customers in the restaurant increase.
- Space Complexity – How much space is required in the restaurant per customer, as the number of customers increase.
Measuring the time complexity of the restaurant
To evaluate the time complexity of a restaurant, we need to assess the restaurant’s process:
Restaurant 1
A sit-down restaurant with a limited number of servers, and as the restaurant gets busier, the wait time to get served increases.
For John and Max to get their food, they rely on the server to seat them, take their order, and for the chef to make their food.
There is only one chef cooking food and each meal takes 30 minutes to cook. Meaning for every customer in the restaurant, the wait time for food grows by 30 minutes.
Number of customers x 30 minutes.
Restaurant 2
Restaurant 2 is a buffet, with no reliance on servers for John and Max to eat their meal. The food is ready to eat, as soon as they have paid.
While the wait time to get food will increase as the restaurant gets busier. It does not grow at a fixed rate like restaurant 1.
John and Max may have to wait a few minutes in a queue to get their desired food, but that is as far as it goes.
Space Complexity
Now a restaurant serving meals efficiently is great, but what if they do not have the space to store many customers?
Restaurant 1 can only sit 4 groups of customers at a time while restaurant 2 can store 30 groups of guests at a time.
Meaning during the busiest time of the week for restaurant 1, the guests will have to queue just to get inside.
Comparing the two restaurants
John and Max can see that the buffet looks like the best restaurant to eat food at.
But to be 100% sure, they created a growth hierarchy ranking system. The labels for the growth hierarchy range between 1 and 5.
1 being the most efficient process and 5 being the least efficient:
- Very efficient – no waiting involved at all
- Efficient – Less than 10 minutes worth of waiting.
- Average Efficiency. 10-30 minutes worth of waiting.
- Inefficient. 30 minutes to an hour worth of waiting.
- Very Inefficient – Waiting over an hour.
So let’s evaluate:
Now they decide to score the restaurants based on the least efficient process for each complexity.
Time Complexity
Restaurant 1 – 5
Restaurant 2 – 2
Space Complexity
Restaurant 1 – 5
Restaurant 2 – 1
Restaurant 2 is the clear winner, with the lowest time and space complexity.
John and Max can ease their mind knowing that restaurant 2 is the best choice.
Big O Notation helps you see how algorithms grow as demand gets higher
Moving away from the restaurant example.
This is exactly how you use big O notation to assess how an algorithm grows in Software Engineering.
There is no need to create a plan like this when going to a restaurant. But when building an enterprise system, knowing the consequence of an algorithm you have created is vital.
An inefficient algorithm that authenticates a user on your website may do the job when you have one user.
But what about when your website goes viral and you have 100,000 users on your system at once?
That inefficient algorithm will now be a problem. And when creating a system, it is a lot harder to change an algorithm once you have pushed it to production.
The same goes for a restaurant. Having one chef and a few tables to serve customers is great when you start.
But once you have invested in a building and set up the restaurant, it is a lot more costly to change things.
How Big O Notation is used in Software Engineering?
Time complexity is used to see how long an algorithm will take to process input, as the size of the input grows.
Space complexity is used to judge how much memory the algorithm will take up as the size of the input grows.
A growth hierarchy labels how each line of code within the algorithm grows as the input increases. Then once evaluating the algorithm, our only concern is the least efficient part of the algorithm.
Here is the growth hierarchy:
Now you do not need to worry about each Big O Hierarchy for now.
We will go into detail in a later article. Just know that the top (O(1)) is the most efficient, and the bottom (O(n!)) is the least efficient.
Let’s look at a PHP function and assess the Big O Notation
With Big O Notation we look at and assess every line of code in the body of an algorithm.
In the above example, we have a function that uses a for loop based on the input $numberOfCustomers.
This loops through n number of times, as it is dependent on the input (the number of customers), and as we do not know the size of the input, we label this n.
Knowing this we can see the first line of code is linear, as it grows a set amount as the input increases (we will cover linear growth in a later article).
If we input 2 into the algorithm, the algorithm will loop twice, if we input 3 it will loop three times. Making the growth linear and resulting in a Big O Notation of O(n).
Looking inside the body of the for loop we can see two lines of code.
Two echo statements which print the text ‘Hello’ and the number 4. As this line of code does not change dependent on the input, we can label this as a Constant growth. As there will be no change of output regardless of the input size. Making it a hierarchy of O(1).
Again you do not need to understand the hierarchy, this is just to show you the process of measuring an algorithm.
Out of the 3 lines of code with hierarchy labels. The least inefficient part of the algorithm is the for loop on the first line with a Big O of O(n).
And as our only concern is the least efficient O notation, the algorithm has a big O Notation of O(n).
Why Big O Notation Will Make You A Better Software Engineer
Understanding the impact of an algorithm can reduce the costs of an enterprise system on a large scale.
Anyone can learn how to glue code together and make a program work. But what separates great Software Engineers from good Software Engineers, is the ability to detect and write efficient algorithms.
Software-minded companies understand the need to scale systems efficiently, and they use Big O Notation interview questions to find talented Software Engineers.
Tune in for the next article, where we will teach you how to identify each Big O Notation within the growth hierarchy.
