Time Complexity Analysis
Master Big O Notation and understand algorithm efficiency through mathematical analysis of best, worst, and average cases.
1. Big O Notation
Mathematical Way to Describe Efficiency
Big O Notation is a mathematical notation that describes the limiting behavior of a function when the argument tends toward infinity. In computer science, it’s used to classify algorithms by how their runtime or space requirements grow as input size grows.
Growth Rate Visualization
Measures Time or Space Growth
Big O describes the upper bound of complexity in the worst-case scenario, helping developers understand how an algorithm will scale with larger inputs.
Constant Time
O(1)
Runtime doesn’t change with input size. Example: Array access by index.
Logarithmic Time
O(log n)
Runtime grows logarithmically. Example: Binary search in sorted array.
Linear Time
O(n)
Runtime grows linearly with input size. Example: Simple linear search.
Quadratic Time
O(n²)
Runtime grows quadratically. Example: Nested loops (Bubble Sort).
Common Notations Hierarchy
| Notation | Growth Rate | Example | Input Size: 10 | Input Size: 100 |
|---|---|---|---|---|
| O(1) | Constant | Array Access | 1 operation | 1 operation |
| O(log n) | Logarithmic | Binary Search | ~4 operations | ~7 operations |
| O(n) | Linear | Linear Search | 10 operations | 100 operations |
| O(n log n) | Linearithmic | Merge Sort | ~33 operations | ~664 operations |
| O(n²) | Quadratic | Bubble Sort | 100 operations | 10,000 operations |
| O(2ⁿ) | Exponential | Tower of Hanoi | 1,024 operations | 1.26e+30 operations |
Helps Compare Algorithms
Algorithm Complexity Examples
// O(1) - Constant Time
function getFirstElement(arr) {
return arr[0]; // Single operation
}
// O(n) - Linear Time
function findElement(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1; // n operations in worst case
}
// O(n²) - Quadratic Time
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
// n * n operations ≈ n²
}
// O(log n) - Logarithmic Time
function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
let 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; // log₂(n) operations
}
2. Best, Worst, Average Cases
Best Case: Minimum Operations
The scenario where the algorithm performs the minimum number of operations. This occurs with the most favorable input.
Best Case Examples
// Linear Search - Best Case O(1)
// Target is at first position
function linearSearchBest(arr, target) {
// Best case: target at arr[0]
return arr[0] === target ? 0 : -1;
}
// Binary Search - Best Case O(1)
// Target is at middle position
function binarySearchBest(arr, target) {
// Best case: target at arr[mid]
return arr[Math.floor(arr.length / 2)] === target
? Math.floor(arr.length / 2)
: -1;
}
// Bubble Sort - Best Case O(n)
// Array already sorted
function bubbleSortBest(arr) {
// Best case: array already sorted
// Only need to check once
let swapped = false;
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
swapped = true;
break;
}
}
return swapped ? "Not sorted" : "Sorted";
}
Worst Case: Maximum Operations
The scenario where the algorithm performs the maximum number of operations. This occurs with the least favorable input.
O(1)
Constant Time
No worst case
O(n)
Linear Search
Target not in array
O(n²)
Bubble Sort
Reverse sorted array
O(2ⁿ)
Fibonacci Recursive
Large n values
Average Case: Expected Operations
The expected number of operations when considering all possible inputs with their probabilities. This is often the most useful metric in practice.
| Algorithm | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Linear Search | O(1) | O(n/2) | 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) |
| Insertion 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) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
Used to Analyze Algorithm Performance
Understanding these three cases helps in:
- Choosing the right algorithm for specific use cases
- Predicting performance with real-world data
- Optimizing code based on expected inputs
- Making informed trade-offs between algorithms
- Designing systems that handle edge cases gracefully
Case Analysis Example: Quick Sort
Quick Sort Complexity Analysis
// Quick Sort Cases Analysis
function quickSort(arr) {
if (arr.length <= 1) return arr;
// Choose pivot (affects all cases)
const pivot = arr[Math.floor(arr.length / 2)];
// Partition
const left = arr.filter(x => x < pivot);
const middle = arr.filter(x => x === pivot);
const right = arr.filter(x => x > pivot);
return [...quickSort(left), ...middle, ...quickSort(right)];
}
/* COMPLEXITY ANALYSIS:
Best Case: O(n log n)
- Pivot always divides array in half
- Balanced partitioning
Average Case: O(n log n)
- Random pivot selection
- Expected balanced partitions
Worst Case: O(n²)
- Pivot is always smallest/largest element
- Unbalanced partitioning
- Sorted or reverse sorted array
*/
Project: Complexity Analyzer Tool
Build a tool that analyzes algorithm complexity and visualizes growth rates for different input sizes.
Complexity Analyzer Implementation
class ComplexityAnalyzer {
constructor() {
this.functions = {
constant: (n) => 1,
logarithmic: (n) => Math.log2(n),
linear: (n) => n,
linearithmic: (n) => n * Math.log2(n),
quadratic: (n) => n * n,
exponential: (n) => Math.pow(2, n)
};
this.results = {};
}
analyzeAlgorithm(name, operationCount) {
// Track operations for different input sizes
const sizes = [10, 20, 50, 100, 200, 500, 1000];
this.results[name] = {};
for (let size of sizes) {
const operations = operationCount(size);
this.results[name][size] = operations;
// Determine complexity pattern
this.detectPattern(name, operations, size);
}
return this.results[name];
}
detectPattern(name, operations, size) {
// Compare with known growth patterns
for (const [pattern, func] of Object.entries(this.functions)) {
const expected = func(size);
const ratio = operations / expected;
// Check if ratio is relatively constant
if (Math.abs(ratio - 1) < 0.5) {
console.log(`${name} shows ${pattern.toUpperCase()} pattern`);
return pattern;
}
}
}
visualizeResults() {
// Create chart visualization
const chartData = {
labels: Object.keys(this.results[Object.keys(this.results)[0]]),
datasets: []
};
for (const [name, data] of Object.entries(this.results)) {
chartData.datasets.push({
label: name,
data: Object.values(data),
borderColor: this.getRandomColor(),
fill: false
});
}
return chartData;
}
getRandomColor() {
return `#${Math.floor(Math.random()*16777215).toString(16)}`;
}
}
// Usage Example
const analyzer = new ComplexityAnalyzer();
// Analyze linear search
analyzer.analyzeAlgorithm('Linear Search', (n) => n);
// Analyze binary search
analyzer.analyzeAlgorithm('Binary Search', (n) => Math.log2(n));
// Get visualization data
const chartData = analyzer.visualizeResults();