# Big O

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;
}

Next