Advanced Algorithm Series: How to Calculate Time Complexity

In the previous article, we explored classic examples of greedy algorithms and understood how greedy algorithms construct globally optimal solutions by selecting locally optimal choices at each step. However, an algorithm’s effectiveness depends not only on its logical structure but also on performance evaluation via complexity analysis. This article focuses specifically on time complexity: how to compute it and how it applies in practical scenarios.

Overview of Time Complexity

Time complexity measures how an algorithm’s runtime scales with respect to the size of its input. It is conventionally expressed using Big-O notation, whose general form is:

Here, $T(n)$ denotes the time required to execute the algorithm, $n$ represents the input size, and $f(n)$ is a function describing the growth rate of execution time (e.g., $n$, $n^2$, $\log n$, etc.). Analyzing time complexity allows us to predict how efficiently an algorithm will perform as input size varies.

Steps for Computing Time Complexity

1. Identify the Basic Operation

First, determine the most significant operation—commonly called the basic operation. The choice depends on the problem context: for sorting algorithms, it may be “comparison” or “swap”; for searching, it’s typically “comparison”.

2. Count Executions of the Basic Operation

Next, estimate how many times the basic operation executes under three scenarios: worst-case, best-case, and average-case. This estimation is usually expressed as a function of input size $n$.

3. Express Using Big-O Notation

Finally, express the count asymptotically using Big-O notation. Recall: when describing time complexity, we focus on behavior as $n \to \infty$, ignoring constant factors and lower-order terms.

Case Studies

Let’s examine time complexity computation through two classic algorithm examples.

Case 1: Bubble Sort

The basic operation in bubble sort is comparison. Consider the following implementation:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

Here, the outer loop runs $n$ times. In the worst case (e.g., when the array is reverse-sorted), the inner loop executes approximately $n - i - 1$ times for each $i$. Thus, total comparisons in the worst case are:

Therefore, bubble sort has time complexity:

Case 2: Binary Search

Binary search is an efficient searching algorithm whose basic operation is also comparison.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

At each iteration, the search space halves. Hence, the number of iterations needed to reduce the interval from size $n$ down to 1 satisfies:

So the time complexity is:

Optimizing Time Complexity

To reduce time complexity, we can apply various optimization strategies—such as adopting more efficient data structures, choosing superior algorithms (e.g., replacing bubble sort with quicksort), or leveraging techniques like dynamic programming.

For instance, storing values and their indices in a hash table reduces lookup time complexity from $O(n)$ to $O(1)$.

Summary

This article introduced time complexity and its calculation methodology—from identifying basic operations and estimating their execution counts, to expressing results using Big-O notation. Through concrete examples, we gained intuitive insight into how different algorithms scale with input size. Understanding these concepts is essential for selecting appropriate algorithms and improving overall program efficiency.

In the next article, we’ll delve into space complexity analysis—a key component of algorithmic complexity—providing further guidance for your continued learning journey.