What Is Big O Notation? A Beginner's Explanation
Big O Notation Explained with Clear Examples
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.
File Size | Physical Transfer | Electronic Transfer |
1 MB | Take Time: Time remains constant, independent of file size | Quickly: The time taken to transfer a file increases with the size of the file. |
1 TB or Large | It can be done in a day | This size of file can take more than one day to transfer |
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.
Find 1 - It is at the beginning of the array.
Find 8 - It is at the end of the array.
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.
Find 1 - Ω time complexity Best Case
Find 4 - Θ time complexity Average Case
Find 8 - O time complexity Worst Case
Runtime complexity of an algorithm
Complexity | Name | Sample |
O(1) | Constant | A simple add number function |
O(N) | Linear | Loop through numbers from 1 to n |
O(log N) | Logarithmic | Find an element in a sorted array |
O(N²) | Quadratic | Nested Loops |
O(1) - Order of 1
O(N) - Order of N
O(log N) - Order of log N
O(N²) - Order of N²