¶ Overview
Time complexity is a measure of how the running time of an algorithm increases as the input size grows. It helps us understand the performance of an algorithm and predict how it behaves with large inputs. Time complexity is commonly expressed using Big-O notation.
¶ Big-O Notation
Big-O notation describes the worst-case scenario of an algorithm’s running time, so we know the maximum time an algorithm could take. It’s written as O(...), where the ... shows how the runtime scales with input size.
¶ Common Time Complexities (from fast to slow)
¶ 1. O(1) - Constant Time
Fastest, no matter the input size.
The algorithm takes the same amount of time, regardless of the input size. Eg. Looking up a value in a hash map or accessing an array element by index.
Example: Accessing an element in an array by its index.
function getFirstElement(array) {
return array[0]; // Always takes constant time
}
¶ 2. O(log n) - Logarithmic Time
Efficient for large data sets; divides the problem in halves.
The running time grows slower as the input size increases, often seen in algorithms that divide the problem in half each time. EG Searching in a sorted array using binary search.
Example: Binary search on a sorted array.
function binarySearch(array, target) {
let left = 0, right = array.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (array[mid] === target) return mid;
else if (array[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
¶ 3. O(n) - Linear Time
Simple loop through all elements, time grows linearly.
The running time increases directly with the size of the input. Eg. Finding the maximum element in an unsorted list.
Example: Looping through an array of size n.
function printAllElements(array) {
for (let i = 0; i < array.length; i++) {
console.log(array[i]); // Runs n times for n elements
}
}
¶ 4. O(n²) - Quadratic Time
Not great for large inputs, time grows quickly due to nested loops.
The running time grows quadratically as the input size increases. EG Comparing every pair of elements in a list (e.g., bubble sort).
Every additional loop multiplier the time taken! This -
can- will escalate quickly and is likely to
Example: Nested loops where each loop runs n times.
function printAllPairs(array) {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
console.log(array[i], array[j]); // Runs n * n times
}
}
}