On Big O Notation
Big O notation is a mathematical concept used in computer science to describe the time complexity and space complexity of algorithms.
What is Big O Notation
- Big O notation expresses the upper bound of an algorithm’s growth rate.
- It describes the worst-case scenario for how much time or space an algorithm will need as the input size (typically denoted as n) increases.
- The “O” stands for “Order of” and helps classify algorithms into categories based on their scalability.
Why Big O Matters
- Performance Prediction: Understand how your algorithm will behave with larger datasets
- Algorithm Comparison: Compare different solutions objectively
- Resource Planning: Estimate computational requirements
- Optimization: Identify bottlenecks and areas for improvement
Common Big O Complexities
| Big O Notation | Name | Description | Example |
|---|---|---|---|
| O(1) | Constant | Same time regardless of input size | Array access by index |
| O(log n) | Logarithmic | Time increases logarithmically | Binary search |
| O(n) | Linear | Time increases linearly with input | Simple array traversal |
| O(n log n) | Linearithmic | Combination of linear and logarithmic | Merge sort, heap sort |
| O(n²) | Quadratic | Time increases quadratically | Nested loops, bubble sort |
| O(n³) | Cubic | Time increases cubically | Triple nested loops |
| O(2ⁿ) | Exponential | Time doubles with each input increase | Recursive Fibonacci |
| O(n!) | Factorial | Extremely poor scaling | Traveling salesman (brute force) |
How to Calculate Big O
Analyze Loops
- Single loop: O(n)
- Nested loops: O(n²)
- Loop that divides the problem: O(log n)
Common Data Structure Operations
Arrays
- Access: O(1)
- Search: O(n)
- Insertion: O(n) (worst case)
- Deletion: O(n) (worst case)
Linked Lists
- Access: O(n)
- Search: O(n)
- Insertion: O(1) (if you have the reference)
- Deletion: O(1) (if you have the reference)
Hash Tables
- Access: O(1) average, O(n) worst case
- Search: O(1) average, O(n) worst case
- Insertion: O(1) average, O(n) worst case
- Deletion: O(1) average, O(n) worst case
Binary Search Trees (Balanced)
- Access: O(log n)
- Search: O(log n)
- Insertion: O(log n)
- Deletion: O(log n)
Practical Examples in java
O(1) - Constant Time
Array Access by Index
public class ConstantTimeExample {
public static int getFirstElement(int[] arr) {
return arr[0]; // Always takes the same time regardless of array size
}
public static int getElementAtIndex(int[] arr, int index) {
return arr[index]; // Direct access is always O(1)
}
}
O(n) - Linear Time
public class ArraySum {
public static long calculateSum(int[] arr) {
long sum = 0;
for (int num : arr) { // Single pass through array
sum += num;
}
return sum;
}
}
O(n²) - Quadratic Time
public class QuadraticTimeExample {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) { // Outer loop: n iterations
for (int j = 0; j < n - i - 1; j++) { // Inner loop: up to n iterations
if (arr[j] > arr[j + 1]) {
// Swap elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) { // Nested loops = O(n²)
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
O(log n) - Logarithmic Time
Binary Search
public class LogarithmicTimeExample {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Avoid overflow
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1; // Problem size halved each iteration
}
}
return -1; // Not found
}
// Recursive version
public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binarySearchRecursive(arr, target, mid + 1, right);
} else {
return binarySearchRecursive(arr, target, left, mid - 1);
}
}
}
O(n log n) - Linearithmic Time
Merge Sort
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid); // O(log n) levels
mergeSort(arr, mid + 1, right); // O(log n) levels
merge(arr, left, mid, right); // O(n) work per level
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, 0, arr, left, temp.length);
}
}
Space Complexity
Big O also applies to space complexity - how much memory an algorithm uses:
O(1): Uses constant extra spaceO(n): Uses space proportional to input sizeO(n²): Uses space proportional to input size squared