What Is Big O Notation? A Beginner's Explanation

Big O notation is a mathematical concept used to describe an algorithm's performance or complexity. It shows how the runtime or space needs of an algorithm increase as the input size grow. If the pace of an algorithm is not known, it will be difficult to determine the program's efficiency. Big O notation helps describe how much time an algorithm will take to run as the size of the input grows.

What is Time Complexity?

A way of showing how the runtime of a function increases as the size of an input increases

What is Space Complexity?

Space complexity is a way of showing how the memory usage of a function increases as the size of the input increases.

Let's understand with an example

Imagine a scenario where you have a file on your hard drive and you need to send it to your friend you need to send the file as soon as possible

Send it via email, FTP, or another electronic transfer method.

Performance variation of an algorithm based on input

Let's understand with an example.

Suppose we want to buy a brand-new car. Obviously, we want to know more about the car's performance, which means we are interested in knowing how many liters of petrol it takes to drive 100 miles.

In the case of a car, there is no standard answer. Even though the manual mentions that it takes 70 liters of petrol for 100 miles, this information may not be correct since a car performs differently based on the conditions.

• City Traffic - 20 L

• Highway - 10 L

• Mixed Condition - 15 L

So, here we see that the same car performs differently based on the conditions in which we drive it.

Similarly, based on the conditions given, an algorithm performs differently.

There are three scenarios for measuring any given algorithm:

• Best Case

• Average Case

• Worst Case

Three Greek letters are used to define the cases of an algorithm.

Omega (Ω), Theta (Θ), and Omicron (O) also known as Big O

Let's consider an example

We have an array containing a list of numbers, and we need to find a specific number.

1. Find 1 - It is at the beginning of the array.

2. Find 8 - It is at the end of the array.

3. Find 4 - It is at the 4th position in the array.

So, finding 1 is quick and easy, but to find 8, we need to go through the entire array and check each element until we reach the end.

1. Find 1 - Ω time complexity Best Case

2. Find 4 - Θ time complexity Average Case

3. Find 8 - O time complexity Worst Case

Runtime complexity of an algorithm

• O(1) - Order of 1

• O(N) - Order of N

• O(log N) - Order of log N

• O(N²) - Order of N²