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
some tricks
swop 2 numbers
int a = 5,
int b = 10;
a = a ^ b; // step 1
b = a ^ b; // step 2: (a ^ b) ^ b → a
a = a ^ b; // step 3: (a ^ b) ^ a → b
System.out.println("a = " + a + ", b = " + b); // a = 10, b = 5
Important notes
- Works only with primitive integral types (int, long, short, byte, char).
- If a and b refer to the same variable (e.g., swapping an element with itself in an array), this method zeroes the value.
mid point
int mid = L + (R - L) / 2;
If L and R are large (for example, close to Integer.MAX_VALUE ≈2.1 billion), their sum can overflow the 32-bit signed range before the division happens, producing a negative or wrap-around value. Splitting the computation into (R - L) prevents this overflow because the difference between two valid indices is guaranteed to fit in the range even when their sum does not. Once the smaller, safe difference is calculated, adding L cannot overflow either: the result is always between L and R.