Master Big O notation for your next DSA interview. Learn how to calculate time and space complexity with clear examples of O(1), O(n), O(n²), and O(log n).
Big O notation describes how the runtime or memory usage of an algorithm grows relative to the input size. It answers: "If I double the input, what happens to the time/memory?"
It focuses on the worst case and dominant terms — we drop constants and lower-order terms.
f(n) = 3n² + 5n + 100 → O(n²)
Two solutions can both be "correct" but one might take 1ms and the other 10 minutes on large inputs. Big O helps you reason about this before writing a single line of code.
Runtime doesn't change regardless of input size.
public int getFirst(int[] arr) {
return arr[0]; // always one operation
}Input is halved each step. Very efficient.
public int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}One operation per element.
public int findMax(int[] arr) {
int maxVal = arr[0];
for (int num : arr) { // n iterations
if (num > maxVal) {
maxVal = num;
}
}
return maxVal;
}Typical of efficient sorting algorithms.
// Merge sort, heap sort, Java's Arrays.sort()
Arrays.sort(arr); // O(n log n)Nested loops over the same input.
public void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) { // n
for (int j = 0; j < arr.length - 1; j++) { // n
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}Each step doubles the work. Avoid for large inputs.
public int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2); // two recursive calls each time
}O(2n) → O(n)
O(500) → O(1)
O(n² + n) → O(n²)
O(n + log n) → O(n)
public void func(int[] a, int[] b) {
for (int x : a) { // O(a)
System.out.println(x);
}
for (int y : b) { // O(b)
System.out.println(y);
}
}
// Total: O(a + b), NOT O(n)for (int i : arr) { // O(n)
for (int j : arr) { // O(n)
// ... // O(n²) total
}
}Space complexity measures extra memory used (not counting the input itself).
public int sumList(int[] arr) {
int total = 0; // O(1) space — just one variable
for (int n : arr) {
total += n;
}
return total;
}
public List<Integer> doubleList(int[] arr) {
List<Integer> result = new ArrayList<>(); // O(n) space — new list relative to input
for (int n : arr) {
result.add(n * 2);
}
return result;
}| Operation | Array | Linked List | Hash Table | BST |
|---|---|---|---|---|
| Access | O(1) | O(n) | O(1) | O(log n) |
| Search | O(n) | O(n) | O(1) | O(log n) |
| Insert | O(n) | O(1) | O(1) | O(log n) |
| Delete | O(n) | O(1) | O(1) | O(log n) |