Understanding algorithm efficiency and performance
Time Complexity measures how an algorithm's execution time changes as the input size grows. It helps you choose the most efficient algorithm for your problem.
Why it matters: Understanding time complexity allows you to predict performance, especially with large datasets, and make informed decisions about which algorithm to use.
Constant Time
Execution time stays the same regardless of input size.
Example: Accessing an array element by index
Logarithmic Time
Time grows very slowly as input increases. Very efficient.
Example: Binary search in a sorted array
Linear Time
Time grows proportionally with input size.
Example: Finding an item in an unsorted array
Linearithmic Time
Common in efficient sorting algorithms.
Example: Merge sort, Quick sort
Quadratic Time
Becomes slow with large inputs. Often involves nested loops.
Example: Bubble sort, Selection sort
Exponential Time
Very slow. Avoid for large inputs when possible.
Example: Recursive Fibonacci (naive approach)
See how different time complexities scale as input size increases
At n=10, notice how O(1) always performs just 1 operation, while O(2ⁿ) requires 1,024 operations!
Try moving the slider to see how quickly exponential complexity grows.
function getFirstElement(arr) {
return arr[0]; // Always takes the same time
}
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1; // Time grows with array size
}
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr; // Nested loops = n × n operations
}
| Algorithm | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | O(1) |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |