Time Complexity — Big O and Master Theorem

Time Complexity

Time complexity describes how the running time of an algorithm grows as the input size grows. It does not measure exact seconds on a particular computer. Instead, it estimates how many basic operations the algorithm performs.

This helps us compare algorithms in a machine-independent way. A solution that looks fast for small input may become very slow for large input, so time complexity is one of the most important tools in algorithm analysis.

Why Time Complexity Matters

Two algorithms may solve the same problem correctly, but their performance can be very different when the input becomes large.

• Better scalability: Efficient algorithms continue to perform well as data grows.
• Lower cost: Faster algorithms reduce CPU time and server usage.
• Improved user experience: Good time complexity leads to faster applications.
• Smarter problem solving: It helps us choose the right approach before coding.

What Does Time Complexity Measure?

Time complexity usually measures the number of basic operations performed by an algorithm, such as:

• comparisons
• assignments
• arithmetic operations
• loop iterations
• recursive calls

We usually express time complexity using Big O notation, which focuses on the dominant growth term and ignores minor constants.

How to Calculate Time Complexity

The following rules are commonly used while analyzing code:

Common Time Complexity Classes

1. O(1) - Constant Time

The running time does not depend on the size of the input. The algorithm performs a fixed number of operations.

def get_first(arr):
    return arr[0]

def is_even(n):
    return n % 2 == 0

def swap(a, b):
    return b, a

2. O(log n) - Logarithmic Time

The running time grows slowly because the problem size is reduced by a constant factor in each step. Binary Search is the classic example.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

# Each step cuts the search space in half.

3. O(n) - Linear Time

The algorithm processes each element once, so running time grows directly with input size.

def find_max(arr):
    max_val = arr[0]

    for num in arr:
        if num > max_val:
            max_val = num

    return max_val

4. O(n log n) - Linearithmic Time

This often appears in efficient divide-and-conquer algorithms such as Merge Sort and Heap Sort. The problem is divided in logarithmic levels, and each level does linear work.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

# Recurrence: T(n) = 2T(n/2) + O(n)
# Result: O(n log n)

5. O(n^2) - Quadratic Time

Quadratic time usually appears when one loop is nested inside another loop over the same input.

def print_pairs(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            print(arr[i], arr[j])

# Number of pair checks grows roughly as n^2.

6. O(2^n) - Exponential Time

Exponential time appears in algorithms where each step creates multiple recursive branches. These algorithms become impractical very quickly.

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# Creates many repeated recursive calls.
# Time complexity is exponential.

Best Case, Average Case, and Worst Case

An algorithm may not behave the same way for every input. That is why time complexity is often discussed in three forms:

Analyzing Loops

Loops are one of the easiest places to estimate complexity.

# O(n)
for i in range(n):
    print(i)

# O(n^2)
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n)
i = 1
while i < n:
    print(i)
    i = i * 2

# O(n)
for i in range(n):
    print(i)
for j in range(n):
    print(j)

Important idea:

• Sequential loops usually add.
• Nested loops usually multiply.
• Loops that repeatedly divide or double a value are often logarithmic.

Analyzing Recursion

Recursive algorithms are often analyzed using a recurrence relation. A recurrence shows how the work for size n depends on smaller inputs.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

# T(n) = T(n - 1) + O(1) -> O(n)


def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1

    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    return binary_search_recursive(arr, target, left, mid - 1)

# T(n) = T(n / 2) + O(1) -> O(log n)

Amortized Time Complexity

Amortized analysis studies the average cost of a sequence of operations when most operations are cheap and a few are expensive.

Master Theorem

The Master Theorem is a shortcut for solving recurrences of the form T(n) = aT(n / b) + f(n).

Example: Merge Sort has T(n) = 2T(n / 2) + O(n). Here, a = 2 and b = 2. Since n^(log_b a) = n, this falls under Case 2, so the result is Theta(n log n).

Real-World Impact of Time Complexity

Practical Optimization Ideas

• Use hashing to replace nested loops when possible.
• Use binary search on sorted data instead of linear search.
• Use dynamic programming to avoid repeated recursive work.
• Prefer single-pass logic over sorting when sorting is unnecessary.
• Choose divide-and-conquer algorithms for large data where appropriate.

# O(n^2)
def two_sum_slow(arr, target):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == target:
                return [i, j]
    return None


# O(n)
def two_sum_fast(arr, target):
    seen = {}

    for i, num in enumerate(arr):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

    return None

Common Mistakes in Time Complexity Analysis

• Counting actual seconds instead of counting growth in operations.
• Ignoring the effect of nested loops.
• Forgetting to simplify expressions like O(3n + 10) to O(n).
• Assuming recursive code is always slow without analyzing the recurrence.
• Focusing only on best case and ignoring worst-case behavior.

Key Takeaways

• Time complexity describes how running time grows with input size.
• Big O is commonly used to express worst-case growth.
• Loops, nested loops, logarithmic reduction, and recursion are the main patterns to analyze.
• O(1), O(log n), and O(n) scale well, while O(n^2) and O(2^n) become expensive quickly.
• Understanding time complexity helps you choose practical and scalable algorithms.