These are just a few examples, and there are many other Big O algorithms with varying time complexities. It’s important to understand the time complexity of an algorithm in order to choose the most efficient one for a given task.
There are six major types of complexities (time and space):
- Constant time: O(1) - Excellent/Best
- Linear time: O(n) - Fair
- Logarithmic time: O(n log n) - Bad
- Quadratic time: O(n^2) - Horrible/Worst
- Exponential time: O(2^n) - Horrible/Worst
- Factorial time: O(n!) - Horrible/Worst
O(1) - Constant time algorithm
Python
def constant_algo(items):
result = items[0] * items[0]
return result
C
int constant_algo(int items) {
int result = items * items;
return result;
}
This algorithm performs a single operation and always takes the same amount of time to run, regardless of the input size.
O(n) - Linear time algorithm
Python
def linear_algo(items):
for item in items:
print(item)
C
void linear_algo(int items) {
for (int i = 0; i < items; i++) {
printf("%d ", i);
}
printf("\n");
}
This algorithm performs an operation for each item in the input, so the time it takes to run increases linearly with the input size.
O(n^2) - Quadratic time algorithm
Python
def quadratic_algo(items):
for item1 in items:
for item2 in items:
print(item1, item2)
C
void quadratic_algo(int items) {
for (int i = 0; i < items; i++) {
for (int j = 0; j < items; j++) {
printf("(%d, %d) ", i, j);
}
printf("\n");
}
}
This algorithm performs an operation for every pair of items in the input, resulting in a nested loop and a quadratic time complexity.
O(log n) - Logarithmic time algorithm
Python
def binary_search(items, value):
low = 0
high = len(items) - 1
while low <= high:
mid = (low + high) // 2
if items[mid] == value:
return mid
elif items[mid] < value:
low = mid + 1
else:
high = mid - 1
return -1
This algorithm performs a binary search on a sorted list, which divides the input size in half with each iteration, resulting in a logarithmic time complexity.
Rust
fn binary_search(items: &[i32], value: i32) -> i32 {
let mut low = 0;
let mut high = items.len() - 1;
while low <= high {
let mid = (low + high) / 2;
if items[mid] == value {
return mid as i32;
} else if items[mid] < value {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}