Big O Notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it's used to classify algorithms according to how their run time or space requirements grow as the input size grows.
| Notation | Name | Description | Example |
|---|---|---|---|
| O(1) | Constant | Runtime is independent of input size | Accessing an array element by index |
| O(log n) | Logarithmic | Runtime grows logarithmically with input size | Binary search |
| O(n) | Linear | Runtime grows linearly with input size | Linear search |
| O(n log n) | Linearithmic | Runtime grows by n log n | Efficient sorting algorithms (Merge sort, Heap sort) |
| O(n²) | Quadratic | Runtime grows quadratically with input size | Simple sorting algorithms (Bubble sort, Insertion sort) |
| O(n³) | Cubic | Runtime grows cubically with input size | Simple matrix multiplication |
| O(2ⁿ) | Exponential | Runtime doubles with each addition to the input | Recursive calculation of Fibonacci numbers |
| O(n!) | Factorial | Runtime grows factorially with input size | Brute force solution to the traveling salesman problem |
↑
│
│ O(n!)
│ ↗
│ ↗
│ ↗
│ ↗
│ ↗
│ ↗
│ ↗
│ ↗
│ ↗ O(2ⁿ)
│ ↗ ↗
│ ↗ ↗
│ ↗ ↗
│ ↗ ↗ O(n²)
│ ↗ ↗
│ ↗ ↗
│ ↗ ↗ O(n log n)
│ ↗ ↗ ↗
│ ↗ ↗ ↗
│ ↗ ↗ ↗ O(n)
│ ↗ ↗ ↗
│ ↗ ↗ ↗
│ ↗ ↗ ↗ O(log n)
│ ↗ ↗ ↗ ↗
│ ↗ ↗ ↗ O(1)
│─────────────────────────────────────────────→
Input Size (n)
Python:
def get_first_element(arr):
return arr[0] if arr else NoneJavaScript:
function getFirstElement(arr) {
return arr.length > 0 ? arr[0] : null;
}Python:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1JavaScript:
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}Python:
def find_max(arr):
if not arr:
return None
max_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
return max_valJavaScript:
function findMax(arr) {
if (arr.length === 0) {
return null;
}
let maxVal = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
}
return maxVal;
}Python:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arrJavaScript:
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}Space complexity refers to the amount of memory an algorithm uses relative to the input size.
| Notation | Description | Example |
|---|---|---|
| O(1) | Constant space | Variables that don't depend on input size |
| O(n) | Linear space | Arrays or objects that grow with input size |
| O(n²) | Quadratic space | 2D arrays that grow with input size |
- Avoid nested loops when possible - They often lead to O(n²) time complexity
- Use appropriate data structures - Hash tables can reduce search time from O(n) to O(1)
- Consider divide and conquer approaches - They can reduce complexity from O(n) to O(log n)
- Be mindful of recursive calls - They can lead to O(2ⁿ) complexity if not optimized
- Use dynamic programming - It can optimize recursive solutions with overlapping subproblems
- Analyze both time and space complexity - Sometimes you can trade one for the other
- Identify the basic operations - Find the operations that are executed most frequently
- Count the number of operations - Determine how many times each operation is executed
- Express in terms of input size - Relate the operation count to the input size
- Drop constants and lower-order terms - Focus on the dominant term as input size grows
- Use the worst-case scenario - Consider the maximum number of operations that could be required