What is Time Complexity?

Time Complexity tells us how the running time of an algorithm grows when the input size n increases.

It is commonly represented using Big O Notation.

Asymptotic Notations

int arr[] = {1, 2, 3, 4};
cout << arr[2];

Direct access takes O(1).

for (int i = 0; i < n; i++) {
    cout << arr[i];
}

Loop runs n times → O(n).

Why O(log n)?

At each comparison, half of the tree is eliminated.

Example: Binary SearchTime Complexity: O(log n)

The search space is repeatedly divided in half.

Divide: The array is repeatedly split in half, creating log₂(n) levels.

Merge: At each level, all n elements are merged exactly once.

Total: O(n) × O(log n) = O(n log n). This is why Merge Sort has O(n log n) time complexity in the best, average, and worst cases.

Examples:
Merge Sort
Heap Sort
Quick Sort (Average)

Time Complexity: O(n log n)

5. O(n²) – Quadratic

 for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cout << i << j;
    }
}

n × n = n² Time Complexity: O(n²)

For n = 3 → 3 x 3 = 9 operations.

 for (int i = 0; i < n; i++)
    cout << A[i];

for (int j = 0; j < n; j++)
    cout << B[j];

Nested Loops

 for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        cout << i << j;

 O(n) × O(n) = O(n²)

Complexity Order

 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

Lower complexity = generally better performance for large inputs.