Big O notations

The Time complexity basics

Algorithmic Time Complexities (BIG-O Notations)

1. Constant Time Loop (O(1)):

for (int i = 0; i < 10; i++) {
    // Constant time operations
    System.out.println("Hello");
}

In this case, the loop has a constant number of iterations (10), so its time complexity is O(1).

2. Linear Time Loop (O(n)):

for (int i = 0; i < n; i++) {
    // Linear time operations
    System.out.println(i);
}

The time complexity of this loop is O(n) because the number of iterations is directly proportional to the size of the input n.

3. Nested Loops:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        // Constant time operations
        System.out.println(i + ", " + j);
    }
}

The time complexity of nested loops is the product of their individual complexities. In this case, it’s O(n * m).

4. Logarithmic Time Loop (O(log n)):

int i = n;
while (i > 0) {
    // Constant time operations
    i = i / 2;
}

The time complexity of this loop is O(log n) because the loop iterates logarithmically with respect to the input size.

5. Quadratic Time Loop (O(n²)):

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // Constant time operations
        System.out.println(i + ", " + j);
    }
}

The time complexity of this loop is O(n²) because it performs n * n iterations.

It’s important to analyze the loops in your algorithm and understand how the number of iterations scales with the input size. The overall time complexity of your algorithm is often determined by the loop with the highest time complexity.

6. Linearithmic Time Loop (O(n log n)):

for (int i = 0; i < n; i++) {
    // Logarithmic time operations
    for (int j = 1; j < n; j *= 2) {
        System.out.println(i + ", " + j);
    }
}

The time complexity of this loop is O(n log n), where the inner loop iterates logarithmically with respect to the outer loop.

7. Cubic Time Loop (O(n³)):

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            // Constant time operations
            System.out.println(i + ", " + j + ", " + k);
        }
    }
}

8. Exponential Time Loop (O(2^n)):

exponentialLoop(int n) {
    if (n <= 0) {
        return;
    }
    exponentialLoop(n - 1);  // Recursion with exponential growth
}

The time complexity of this recursive function is O(2^n) because each call roughly doubles the number of recursive calls.

9. Factorial Time Loop (O(n!)) — Not Common:

factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

The time complexity of this recursive factorial function is O(n!), where n! (n factorial) denotes the product of all positive integers up to n.

It’s essential to choose algorithms and data structures that result in efficient time complexities based on the problem requirements and input sizes. In practice, lower time complexities (closer to O(1), O(log n), O(n), etc.) are generally more desirable for efficient algorithms.