What Is Big O Notation and Why Software Engineers Must Know This Concept for Their Next Tech Interview
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…