What is Big O?
"Big O" is a notation used to measure the efficiency of an algorithm in terms of execution time or memory usage, also known as complexity.
How does it work?
In simple terms, Big O describes how the execution time (or memory usage) grows as the input data size (represented by the letter n) increases.
Main complexity classes
Constant Complexity
-
Representation:
O(1) - The algorithm's cost is independent of the size of n. Instructions are executed a fixed number of times.
// Regardless of the size of the array,
// the instruction is executed only once
public static int example1(int[] array) {
return array[array.length / 2];
}
Linear Complexity
-
Representation:
O(n) - The algorithm's cost grows linearly with the input size. Each input element needs to be processed once.
// This algorithm iterates through each element of the array once, summing the values.
public static int example2(int[] array) {
int sum = 0;
for (int i = 0; i < array.length; i++) {
sum += array[i];
}
return sum;
}
Quadratic Complexity
-
Representation:
O(n²) - The algorithm's cost increases quadratically with the size of n. It typically occurs when there are two nested loops.
// This algorithm implements a sorting method, the Bubble Sort
public static void bubbleSort(int[] array) {
int temp;
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
Logarithmic Complexity
-
Representation:
O(log n) - The algorithm's cost grows logarithmically with the size of n. It is common in search algorithms or divide and conquer algorithms.
// This algorithm performs a binary search on a SORTED array
public static int example4(int[] array, int key) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int middle = left + (right - left) / 2;
if (array[middle] == key) {
return middle;
}
if (array[middle] < key) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
Complexity and Optimization
The following graph demonstrates, in terms of time and memory efficiency, which complexities perform better as input parameters tend to infinity:
Graph: https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/
Top comments (0)