DSAAlgorithmsComplexity
Big O Notation Explained
Understanding time and space complexity analysis with practical examples.
6 min read
Big O Notation Explained
Big O notation is a mathematical notation that describes the limiting behavior of a function. In computer science, we use it to classify algorithms according to how their run time or space requirements grow as the input size grows.
Why Does It Matter?
Understanding Big O helps you:
- Compare algorithms objectively
- Predict performance at scale
- Make informed decisions about data structure choices
Common Complexities
O(1) - Constant Time
function getFirst(arr) {
return arr[0]; // Always one operation
}
O(n) - Linear Time
function findMax(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}
O(n²) - Quadratic Time
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;
}
O(log n) - Logarithmic Time
function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
Conclusion
Master Big O notation early - it's the foundation for all algorithm analysis.