AbeerInstead of a lot of gibberish, let's get straight to the point. What is Big O Notation and what is it used for? The clear answer is Big O notation is a way to describe how the performance of an algorithm changes as the size of the input grows. It helps you understand how fast or slow your code will be when processing larger and larger amounts of data.
In simple terms, Big O tells you the worst-case scenario of how long your code will take or how much space it will need as the input gets bigger.
There are different types or kinds of Big O notations that describe how an algorithm behaves as the size of the input grows. These different notations represent different levels of efficiency or performance. Each type tells you how much time or space an algorithm will need based on the input size.
Some Common O Notations
O(1) – Constant Time
When an operation takes the same amount of time to complete, regardless of the size of the input, it’s considered O(1). This means that no matter how large or small the data you're working with, the time to execute the operation is constant and does not increase as the input grows.
Example 1: Accessing an Array Element
let numbers = [10, 20, 30, 40, 50];
// If you want to access an element at a specific index, like:
let num = numbers[2]; // This will give you 30
This operation will always take the same amount of time no matter how big the array is. Whether the array has 5 elements or 5 million, directly accessing numbers[2] will always be O(1) because you're just fetching one value using its index.
Example 2: Assigning a Value
let a = 10;
Example 3: Checking if a Number is Even
function isEven(number) {
return number % 2 === 0;
}
No matter how large the number is, this function will take the same amount of time to run. So, this is also O(1).
O(n) – Linear Time
In O(n), the time it takes to complete an operation increases directly with the size of the input. If the input doubles, the time it takes to execute the operation also doubles. This happens because the algorithm needs to process each item in the input one by one.
Example 1: Looping Through an Array
Imagine you have an array and you want to print every element in it. The time it takes will depend on how many elements are in the array. Here's a simple example:
let numbers = [10, 20, 30, 40, 50];
for (let i = 0; i < numbers.length; i++) {
console.log(numbers[i]);
}
In this example:
If the array has 5 elements, the loop will run 5 times.
If the array has 100 elements, the loop will run 100 times.
If the array has n elements, the loop will run n times.
Example 2: Searching for a Value in an Array
Suppose you want to find whether a specific value exists in an array:
function findValue(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return true;
}
}
return false;
}
In this example:
If the array has 10 elements, the loop might run up to 10 times to find the value.
If the array has 1,000 elements, the loop might run up to 1,000 times.
For n elements, the loop could run n times in the worst case.
So, the larger the array, the longer it takes to check each element, making it O(n).
O(n²) – Quadratic Time
O(n²) means that the time it takes to complete an algorithm increases exponentially as the input size increases. Specifically, if the input size doubles, the time it takes increases four times (because 2² = 4). If the input triples, the time increases nine times (because 3² = 9).
This usually happens when you have nested loops, where one loop iterates over the input and then, inside that loop, another loop also iterates over the same input.
Nested Loops over an Array: Let’s say you have an array and you want to compare each element with every other element in the array. Here’s an example:
let numbers = [10, 20, 30, 40, 50];
for (let i = 0; i < numbers.length; i++) {
for (let j = 0; j < numbers.length; j++) {
console.log(numbers[i], numbers[j]);
}
}
Here’s what’s happening:
The outer loop runs n times (where
nis the length of the array).For each iteration of the outer loop, the inner loop also runs n times.
So, for every single item in the array, you're looping over every item again. If the array has 5 elements, the inner loop runs 5 times for each of the 5 outer loop iterations, making it run a total of 25 times (5 × 5 = 25).
This makes the time complexity O(n²), because for n elements, you’re performing n × n operations.
Summary of O(n²): O(n²) occurs when you have nested loops, where both loops iterate over the same input. The time taken grows quadratically with the size of the input. It’s slower compared to O(n) and O(log n) because the number of operations grows much faster as the input size increases.
Quadratic time is common in algorithms like bubble sort or in problems where you need to compare every pair of items in a dataset.
O(log n) – Logarithmic Time
I think this one needs more attention and carefulness to grasp the concept.
In O(log n), the time does increase as the input size gets larger, but it increases much more slowly compared to other time complexities like O(n) or O(n²).
Here’s the key idea: In O(log n) algorithms, each step reduces the problem size significantly (often by half), which means that as the input gets bigger, the number of additional steps needed doesn’t grow much. In fact, it grows logarithmically, meaning a very slow increase.
Comparing O(n) and O(log n)
O(n) – Linear Time:
If you have 10 items, you might need 10 steps.
If you have 100 items, you need 100 steps.
If you have 1,000 items, you need 1,000 steps.
Here, the time grows directly with the input size.
O(log n) – Logarithmic Time:
If you have 10 items, you might need around 4 steps (because log₂(10) ≈ 4).
If you have 100 items, you only need around 7 steps (because log₂(100) ≈ 7).
If you have 1,000 items, you only need around 10 steps (because log₂(1,000) ≈ 10).
Even though the input is growing a lot (from 10 to 1,000), the number of steps (the "time") is only increasing slightly (from 4 steps to 10 steps).
Binary Search
A classic example of O(log n) is binary search. Let’s say you have a sorted array, and you want to find if a target number exists in the array. Instead of checking every number one by one (which would be O(n)), you can cut the search space in half at each step.
Here’s an example of binary search:
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1; // Search the right half
} else {
right = mid - 1; // Search the left half
}
}
return -1; // Target not found
}
How It Works:
You start by comparing the middle element of the array with the target.
If the middle element is the target, you're done.
If the middle element is smaller than the target, you discard the left half of the array and search only in the right half.
If the middle element is larger, you discard the right half and search in the left half.
Each time, you're cutting the array in half.
Final Words
Big O Notation is used to describe how the time or space complexity of an algorithm changes as the input size grows. It gives us a way to talk about the efficiency of an algorithm, especially as the input gets larger. Big O focuses on the worst-case scenario, helping us understand the upper limit of an algorithm’s performance.
