Articles
Posts Tags Categories Random
Partners
About
About Author Portfolio Terms of Use Privacy Policy Time Travel Donate
More
Settings Funny Tools Useful Websites Student Works Message Board Recent Comments

Contents

Time Complexity

 Published   Updated    1494 words   8 minutes   views
https://raw.githubusercontent.com/Josh-test-lab/website-assets-repository/refs/heads/main/posts/time%20complexity/cover%20image.webp

Time complexity is used to describe how the computation time of an algorithm grows as the input size increases during its execution. Because the processing capabilities, hardware architecture, and system environment differ across computer devices, comparing algorithms solely based on actual execution time often fails to yield representative and portable conclusions. Therefore, time complexity is usually measured by the “number of basic operations executed,” and asymptotic complexity is employed to analyze the efficiency of algorithms, establishing a hardware-independent and universally applicable performance evaluation method.

Asymptotic Notation

When analyzing algorithms, we typically assume that each basic operation requires the same amount of time. Through time complexity analysis, we can predict the execution efficiency of programs under large-scale inputs, provide a standard for comparing the efficiency of different algorithms, and assist in performance optimization and resource planning. Asymptotic notation is the primary tool for describing time complexity, with Big $O$ notation being the most commonly used.

For example, consider the polynomial function:

$$ T(n) = 4n^2 - 2n + 2 $$

Its time complexity can be categorized as follows:

Big O Notation

Big O notation describes the “asymptotic upper bound” of a function, representing that as the input size becomes sufficiently large, the growth rate of the function will not exceed a certain upper bound. It is commonly used in algorithm analysis to represent the worst-case time complexity. It is defined as follows:

If there exist constants \(c > 0\) and \(n_0 > 0\), and functions $f$ and $g$, such that

$$ 0 \le f(n) \le c \cdot g(n), \quad \forall n \ge n_0, $$

then

$$ f(n) \in O(g(n)) $$

or equivalently,

$$ f(n) = O(g(n)), $$

indicating that the time complexity of function $f$ is bounded above by $O(g(n))$.

For the previous example $T(n)$, we have

$$ T(n) \in O(4n^2 - 100n + 2). $$

However, in asymptotic analysis, we focus on which term dominates the overall growth as $n$ becomes large. For $T(n)$, the following table shows the contributions of each term as $n$ increases:

$n$$4n^2$$- 2n$$2$
14-22
10400-202
10040000-2002

From the table, we can see that as $n$ increases, the highest-degree term grows the fastest and its magnitude far exceeds that of the other terms. Moreover, the asymptotic growth rate is independent of the coefficients. Therefore, Big O notation is usually simplified to the highest-degree term, such as

$$ T(n) = O(n^2). $$

Big Omega Notation

Big-Omega notation describes the “asymptotic lower bound” of a function, indicating that the growth rate of the function will not fall below a certain lower bound. It is commonly used to express the best-case time complexity. It is defined as follows:

If there exist constants \(c > 0\) and \(n_0 > 0\), and functions $f$ and $g$, such that

$$ 0 \le c \cdot g(n) \le f(n), \quad \forall n \ge n_0, $$

then

$$ f(n) \in \Omega(g(n)) $$

or equivalently,

$$ f(n) = \Omega(g(n)). $$

For the previous example $T(n)$, since the quadratic term dominates the overall growth, we can find a constant $c > 0$ (e.g., $c = 1$) such that

$$ c \cdot n^2 \le 4n^2 - 2n + 2, \quad \forall n \ge n_0, $$

thus, the asymptotic lower bound of $T(n)$ can be expressed as

$$ T(n) = \Omega(n^2). $$

Big Theta Notation

Big-Theta notation describes the “asymptotic tight bound” of a function and represents the set of functions that grow at the same rate as $g(n)$. It is defined as follows:

If there exist constants \(c_1 > 0\) and \(c_2 > 0\) and \(n_0 > 0\), such that

$$ 0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n), \quad \forall n \ge n_0, $$

then

$$ f(n) \in \Theta(g(n)) \quad \text{or} \quad f(n) = \Theta(g(n)). $$

In other words, the asymptotic upper and lower bounds of $f(n)$ are both controlled by $g(n)$, hence

$$ f(n) = O(g(n)) \quad \text{and} \quad f(n) = \Omega(g(n)). $$

For the previous example $T(n)$, since

$$ T(n) = O(n^2) \quad \text{and} \quad T(n) = \Omega(n^2), $$

we have

$$ T(n) = \Theta(n^2). $$

Big-Theta notation indicates that the asymptotic growth rate of $T(n)$ is exactly quadratic, neither less nor greater than the order of $n^2$.

Common Time Complexities

When analyzing algorithms, different algorithms have different time complexities. The following table lists common time complexities along with their descriptions:

ComplexityNameDescriptionTypical Examples
$O(1)$Constant TimeExecution time does not change with input sizeAccessing array elements, hash table lookup
$O(\log n)$Logarithmic TimeProblem size is reduced each step (divide-and-conquer)Binary search
$O(n)$Linear TimeAll data must be checked onceTraversing an array, calculating a sum
$O(n \log n)$Linearithmic TimeEfficient sortingMerge sort, heap sort
$O(n^2)$Quadratic TimeNested loop operationsBubble sort, selection sort
$O(2^n)$Exponential TimeComputation grows exponentially with each inputGenerating subsets recursively, brute-force solutions

The approximate growth trends of these complexities for different input sizes ($n$) are shown below:

Input Size ($n$)1101001,000
$O(1)$1111
$O(\log n)$0~3~7~10
$O(n)$1101001,000
$O(n \log n)$0~33~664~9,966
$O(n^2)$110010,0001,000,000
$O(2^n)$21,024~$10^{30}$~$10^{301}$

From the table, we can observe that different time complexities vary greatly in sensitivity to input size. Algorithms with $O(1)$ complexity are almost unaffected by input size, maintaining stable execution time. $O(\log n)$ grows very slowly, so even with large inputs, the additional cost is relatively low. $O(n)$ and $O(n \log n)$ show noticeable differences for medium to large inputs, the latter is slightly slower but still considered efficient. In contrast, $O(n^2)$ grows rapidly, and for large-scale data, execution efficiency drops significantly, often becoming a performance bottleneck.

Python Examples

The different time complexities can be illustrated with simple Python examples:

  • $O(1)$

A constant-time algorithm executes a fixed number of steps regardless of input size. Whether the array length is 10 or 10,000, this function performs only a single access operation.

1
2
3

# O(1)
def get_first_element(arr):
    return arr[0]
  • $O(\log n)$

A logarithmic-time algorithm halves the problem size each step, quickly approaching the solution. It is suitable for divide-and-conquer strategies. For an array of length $n$, at most $\log_2(n)$ comparisons are performed.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# O(log n)
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
  • $O(n)$

A linear-time algorithm needs to traverse the input once; the number of steps is proportional to the input size. For an array of length $n$, it requires $n$ addition operations.

1
2
3
4
5
6

# O(n)
def sum_list(arr):
    total = 0
    for x in arr:
        total += x
    return total
  • $O(n \log n)$

Linearithmic-time algorithms typically appear in efficient sorting or divide-and-conquer strategies. For data of length $n$, the algorithm recursively splits the data and merges results, giving a total computation of approximately $n \times \log_2(n)$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

# O(n log n)
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
  • $O(n^2)$

Quadratic-time algorithms typically involve nested loops, and the computation grows with the square of the input size. For an array of length $n$, it requires $n \times n$ operations.

1
2
3
4
5
6

# O(n^2)
def print_pairs(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n):
            print(arr[i], arr[j])
  • $O(2^n)$

Exponential-time algorithms grow exponentially with input size. Even small $n$ can lead to rapidly increasing computation, common in brute-force or combinatorial problems.

1
2
3
4
5
6
7

# O(2^n)
def generate_subsets(arr):
    if not arr:
        return [[]]
    first = arr[0]
    rest_subsets = generate_subsets(arr[1:])
    return rest_subsets + [[first] + subset for subset in rest_subsets]

Conclusion

Time complexity is a core concept for understanding and designing algorithms. By analyzing how an algorithm’s execution grows with different input sizes, we can effectively evaluate its efficiency and make reasonable trade-offs between performance and resources. Mastering time complexity not only helps in selecting suitable algorithms but also guides program optimization, system design, and strategic planning when dealing with large-scale data.

References

Updated on 2026-01-01 16:05 UTC+0800   48c78f4e
Creative Commons License
 Algorithm, Mathematics, Notes, Python
Back | Home