Computing & HPC Difficulty: Intermediate

Algorithm Complexity and Analysis

Algorithm complexity characterizes the resources (time, space) required by an algorithm as a function of input size. Big-O notation enables comparison of scalability.

Key Points

  • Big-O describes asymptotic upper bounds on growth rates.
  • Time and space complexity are typically functions of input size $n$.
  • Lower bounds and NP-hardness reveal fundamental limits.

Formulas

Big-O definition
$$f(n) = O(g(n)) \iff \exists c, n_0 : \forall n \ge n_0, \; |f(n)| \le c|g(n)|$$
Master theorem
$$T(n) = aT(n/b) + f(n)$$
Matrix multiplication complexity
$$O(n^\omega) \text{ where } \omega < 2.373$$

Code Example

import time

def measure(n):
    start = time.time()
    [i**2 for i in range(n)]
    return time.time() - start

for n in [10**4, 10**5, 10**6]:
    print(n, measure(n))

Applications

Tags

  • big-o
  • complexity
  • algorithms

References

  • Introduction to Algorithms
    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein · MIT Press · source
  • The Design and Analysis of Algorithms
    Dexter C. Kozen · Springer · source

Knowledge Graph