Big O | Agung Pambudi

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

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)

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)

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