An algorithm is a finite, well-defined sequence of computational steps or procedures that takes some value, or set of values, as input and produces some value, or set of values, as output.
Informally, it represents the core logical “idea” behind any reasonable computer program, formulated in a language- and machine-independent way. An algorithm is said to solve a computational problem if it correclty maps every valid input instance to the correct output.
A distinction exists between a computational problem and an instance of that problem:
Sorting Problem: Given a list of numbers, the task is to arrange them in ascending order.
To be considered well-defined and practically useful, an algorithm must meet several rigorous criteria:
Algorithm efficiency describes the relationship between the size of a problem \((n)\) and the computational resources required by an algorithm to solve it. The primary resources of concern are Time Complexity (how execution time or computational steps grow with input size) and Space Complexity (how memmory requirements scale with input size). Although other physical resources such as disk I/O, network communication bandwidth, and energy consumption can be relevant in specific contexts, execution time and memory remain our primary analytical focus because they strongly dictate an application’s scalability.
There are two complementary ways of evaluating algorithm efficiency: empirical performance analysis and theoretical complexity analysis.
| Dimension | Empirical Performance Analysis | Theoretical Complexity Analysis |
|---|---|---|
| Primary Question | “What resources were actually used by this implementation?” | “How do the resource requirements scale abstractly as a function of \(n\)?” |
| Methodology | Measured by running compiled/interpreted code on actual physical hardware under specific conditions. | Mathematically modeled by counting primitive operational steps as a function of input size \(n\). |
| Hardware Dependence | Deeply dependent on the physical machine, operating system, cache hierachy, compiler, and language. | Machine-independent; abstracts away hardware details to evaluate the core algorithm. |
| Example Measures | 2.4 seconds, 500 MB of RAM, 30 Joules. | \(T(n) = 3n + 2\) steps, \(S(n) = n\) memory units. |
To facilitate machine-independent analysis, computer scientists evaluate algorithms on a hypothetical computer called the Random-Access Machine (RAM) model of computation. The RAM model assumes a single-processor computer where instructions are executed strictly sequentially with no concurrency. Under this model:
if, or subroutine call) takes exactly one time step.We measure the run time of an algorithm by counting the number of RAM instructions executed on a given input instance.
An algorithm’s behavior can vary significantly between different inputs of the exact same size \(n\). To summarize this behavior, we define three standard functions over the set of all possible input instances:
Asymptotic analysis is a methodology used to describe the efficiency of algorithms as the input size \(n\) grows arbitrarily large, approaching infinity \(n\to \infty\). In this limit, the exact step count \(T(n)\) becomes less critical than the dominant growth rate.
Asymptotic analysis suppresses constant factors and lower-order terms, because as \(n\) grows, their relative impact is entirely dwarfed by the highest-power term.
Given two running-time functions:
\[ f(n) = 100n \qquad \text{and} \qquad g(n)= n^2+5 \]
For small inputs (\(n<100\)), \(f(n)\) is larger. However, there is a crossover point (\(n_0=100\)), beyond which the quadratic term of \(g(n)\) dominates. As \(n\to \infty\), \(g(n)\) grows infinitely faster than \(f(n)\), making \(f(n)\) asymptotically superior because its resource footprint grows slower.
import numpy as np
import matplotlib.pyplot as plt
n = np.arange(1, 200)
f_n = 100 * n
g_n = n**2 + 5
plt.plot(n, f_n, label='f(n) = 100n')
plt.plot(n, g_n, label='g(n) = n^2 + 5')
# note the crossover point
plt.axvline(x=100, color='gray', linestyle='--', label='Crossover Point (n=100)')
plt.xlabel('Input Size (n)')
plt.ylabel('Running Time')
plt.title('Asymptotic Behavior of Two Functions')
plt.legend()
plt.show()
To formalize these limits, we utilize three primary mathematical notations. Let \(t(n):\mathbb N \to \mathbb R\) bbe the actual running time function of an algorithm, and let \(f(n)\) be an abstract bounding function.
We say that \(t(n)\) is Big-O of \(f(n)\), denoted as \(t(n) \in O(f(n))\), if and only if there exist positive real constants \(c\) and \(n_0\) such that for all \(n \geq n_0\): \[ t(n) \leq c \cdot f(n) \]
This notation characterizes an asymptotic upper bound: eventually, the actual growth rate \(t(n)\) grows no faster than a constant multiple of \(f(n)\). While it is true to state that a linear function \(5n+2\) is \(O(n^2)\) or \(O(n^3)\), we always strive to make the upper bound as tight as possible by reporting \(O(n)\).
To prove that \(t(n) = 5n+2 \in O(n)\), we must find valid positive constants \(c\) and \(n_0\) such that \(5n+2\leq c\cdot n\). Selecting \(c=6\) and \(n_0=3\) yields: \[ 5(3) + 2 = 17 \leq 6(3) = 18 \] thus, for all \(n \geq 3\), the inequality holds, confirming that \(t(n) \in O(n)\).
We say that \(t(n)\) is Big-Omega of \(f(n)\), denoted as \(t(n) \in \Omega(f(n))\), if and only if there exist positive real constants \(c\) and \(n_0\) such that for all \(n \geq n_0\): \[ t(n) \geq c \cdot f(n) \]
This notation characterizes an asymptotic lower bound: eventually, the algorithm’s execution rate will require at least a constant multiple of \(f(n)\) steps for all inputs larger than \(n_0\).
We say that \(t(n)\) is Big-Theta of \(f(n)\), denoted as \(t(n) \in \Theta(f(n))\), if and only if there exist positive real constants \(c_1\), \(c_2\), and \(n_0\) such that for all \(n \geq n_0\): \[ c_1 \cdot f(n) \leq t(n) \leq c_2 \cdot f(n) \]
This notation defines a tight bound, meaning \(t(n)\) and \(f(n)\) grow at the same asymptotic rate within constant scale factors.
The relationship between these three notations can be summarized as follows:
For any two functions \(f(n)\) and \(g(n)\),
\[ f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ and } f(n) = \Omega(g(n)) \]
When simplifying complexity expressions, we adhere to several basic rules of function summation and multilication:
\[ f(n) + g(n) = \Theta(\max(f(n), g(n))) \]
Example: \(n^3+n^2+n+1\to \Theta(n^3)\) because \(n^3\) dominates.
\[ O(c\cdot f(n)) \to O(f(n)) \]
If \(f_1(n)\in O(g_1(n))\) and \(f_2(n)\in O(g_2(n))\), then \(f_1(n)\cdot f_2(n) \in O(g_1(n)\cdot g_2(n))\).
\[ a_mn^m + a_{m-1}n^{m-1} + \dots + a_1n + a_0 \in \Theta(n^m) \]
We systematically drop lower-order terms and drop constant factors.
Example: \(7n^3+20n^2+4n\in O(n^3)\).
To compare algorithms, we arrange common growth functions in a strict dominance hierachy.
We say that a function \(g(n)\) dominates a function \(f(n)\), denoted \(g(n) \gg f(n)\), if and only if:
\[ f(n) \in O(g(n)) \quad \text{and} \quad g(n) \notin O(f(n)) \]
The standard dominance pecking order, including advanced and esoteric analysis function, is:
\[ n! \gg c^n \gg n^3 \gg n^2 \gg n^{1+\epsilon}\gg n\log n \gg \sqrt{n} \gg n \gg \log n \gg 1 \]
def get_first_element(arr):
return arr[0] # Accessing the first element is a constant-time operationPush and Pop operations on a stack structure.def binary_search_digits(n):
count = 0
while n > 0:
n = n // 2 # repeated halving
count += 1
return countInsert and Find operations in a balanced Binary Search Tree (BST) with \(n\) nodes.def find_max_element(arr):
max_val = arr[0]
for element in arr: # traverse the list of size $n$ exactly once
if element > max_val:
max_val = element
return max_valdef merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2 # divide the array into two halves
left_half = merge_sort(arr[:mid]) # recursively sort the left half
right_half = merge_sort(arr[mid:]) # recursively sort the right half
return merge(left_half, right_half)def find_duplicates(arr):
n = len(arr)
for i in range(n):
for j in range(i + 1, n): # nested loop over the array
if arr[i] == arr[j]:
return True
return Falsedef cubic_matrix_multiplication(A, B, n):
C = [[0] * n for _ in range(n)] # Initialize result matrix
for i in range(n):
for j in range(n):
for k in range(n): # Triple nested loop
C[i][j] += A[i][k] * B[k][j]
return Cdef recursive_fibonacci(n):
if n <= 1:
return n
# generate a binary recursion tree of height n
return recursive_fibonacci(n - 1) + recursive_fibonacci(n - 2)def generate_permutations(arr):
if len(arr) == 0:
return [[]] # Base case: one permutation of an empty list
permutations = []
for i in range(len(arr)):
# Generate all permutations of the remaining elements
remaining = arr[:i] + arr[i+1:]
for p in generate_permutations(remaining):
permutations.append([arr[i]] + p)
return permutationsAdvanced algorithmic analysis occasionally encounters more specialized growth classes:
To write efficient code, we must understand the logical layers of data organization.
┌─────────────────────────────────────────────────────────┐
│ 1. Abstract Data Type (ADT) │
│ - Specifies values and supported operations │
│ - "What does the structure do?" (No implementation) │
└────────────────────────────┬────────────────────────────┘
▼
┌─────────────────────────────────────────────────────────┐
│ 2. Data Structure │
│ - Specifies physical arrangement and algorithm │
│ - "How are the operations carried out?" │
└────────────────────────────┬────────────────────────────┘
▼
┌─────────────────────────────────────────────────────────┐
│ 3. Concrete Data Type │
│ - Language-specific physical implementation │
│ - Python list, User-defined class │
└─────────────────────────────────────────────────────────┘
insert, delete, and get, but does not dictate how these operations are implemented.list or a C++ std::vector are concrete data types that implement the List ADT using dynamic arrays.x in collection) at scale:
list (Dynamic Array data structure): Requires \(O(n)\) linear traversal because elements are stored consecutively in memory, necessitating sequential checking.set (Hash Table data structure): Requires \(O(1)\) constant time because the hashing function maps keys directly to specific memory addresses, bypassing traversal.The Selection Sort algorithm repeatedly identifies the minimum remaining unsorted element and exchanges it with the element at the boundary of the sorted partition.
Selection Sort Python Implementation:
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i] # Swap the found minimum element with the first unsorted elementTo compute the exact step complexity \(T(n)\) under the RAM model, we count the number of comprarisons executed in the inner loop:
Summing these steps yields:
\[ T(n) = (n-1) + (n-2) + \dots + 2 + 1 = \sum_{i=0}^{n-1} (n-i-1) = \frac{n(n-1)}{2} = \frac{n^2-n}{2} \]
Applying asymptotic simplification rules (dropping constant factors and lower-order terms):
\[ T(n) \in \Theta(n^2) (\text{quadratic time complexity}) \]
Nested loops are a common source of polynomial time complexity. Consider the naive algorithm for multiplying two \(n \times n\) matrices \(A\) and \(B\) to produce a result matrix \(C\).
Naive Matrix Multiplication Python Implementation
def matrix_multiply(A, B, x, y, z):
"""
A is of size x * y, B is of size y * z, and C will be of size x * z.
"""
C = [[0] * z for _ in range(x)] # Initialize result matrix
for i in range(x):
for j in range(z):
for k in range(y):
C[i][j] += A[i][k] * B[k][j]
return CThe total number of multiplication steps \(M(x, y, z)\) is represented by three nested summations:
\[ M(x, y, z) = \sum_{i=0}^{x-1} \sum_{j=0}^{z-1} \sum_{k=0}^{y-1} 1 = x \cdot z \cdot y \]
Evaluating the nested summations from the innermost outward: 1. The innermost sum of 1 from 1 to \(y\) is simply \(y\): \[ \sum_{k=0}^{y-1} 1 = y \] 2. The sum of the constant \(y\) from 1 to \(z\) yields \(y \cdot z\): \[ \sum_{j=0}^{z-1} y = y \cdot z \] 3. Finally, summing \(y \cdot z\) from 1 to \(x\) gives \(x \cdot y \cdot z\): \[ \sum_{i=0}^{x-1} y \cdot z = x \cdot y \cdot z \]
If we consider the common case of multiplying two square matrices of dimension \(n\times n\) (where \(x=y=z=n\)), the complexity simplifies to:
\[ M(n) = n^3 \in \Theta(n^3) (\text{cubic time complexity}) \]
Divide-and-conquer algorithms operate by recursively calling themselves on smaller instances of a problem. The running time of such recursive structures is formally modeled using recurrence equation.
A recurrence equation describes the overall running time \(T(n)\) of a problem of size \(n\) in terms of the running time of smaller inputs. For a standard divide-and-conquer algorithm that divides a problem into \(a\) subproblems, each of size \(1/b\) of the original, with dividing cost \(D(n)\) and combining cost \(C(n)\), the recurrence relation is:
General Recurrence Equation for Divide-and-Conquer
\[ T(n) = \cases{ \Theta(1), & if $n \leq c$\\ a T(n/b) + D(n) + C(n), & otherwise } \]
For Merge Sort, we assume \(n\) is an exact power of 2 for simplicity. The algorithm divides the array into \(a=2\) subproblems, each of size have exactly \(n/b = n/2\).
Dividing Cost \(D(n)\): Finding the middle of the array takes constant time, \(D(n) = \Theta(1)\).
Combining Cost \(C(n)\): Merging two sorted subarrays of total size \(n\) requires linear time, \(C(n) = \Theta(n)\).
This yields the classical recursive equation:
\[ T(n) = 2 T(n/2) + \Theta(n) \]
To solve this recurrence, we construct a recursion tree:
Level 0: cn Total cost: cn
/ \
Level 1: cn/2 cn/2 Total cost: 2*(cn/2) = cn
/ \ / \
Level 2: cn/4 cn/4 cn/4 cn/4 Total cost: 4*(cn/4) = cn
/ \ / \ / \ / \
...
Level log n: c c c c c c c Total cost: n*c = cn
\[ 2^i \cdot c \cdot \frac{n}{2^i} = c \cdot n \]
\[ T(n) = c\cdot n \cdot (\log n + 1) = c \cdot n \log n + c \cdot n \]
Dropping lower-order terms and constant coefficients, we prove:
\[ T(n) \in \Theta(n \log n) (\text{log-linear time complexity}) \]
When performing complexity analysis on loop structures, the following mathematical closed-form summations are frequently applied:
The sum of the first \(n\) natural numbers:
\[ \sum_{i=1}^{n} i = 1+ 2+ \dots + n = \frac{n(n+1)}{2} \in \Theta(n^2) \]
More generally, for any power \(p\geq 0\):
\[ \sum_{i=1}^{n} i^p \in \Theta(n^{p+1}) \]
A summation where the index affects the exponent:
\[ \sum_{i=0}^{n} a^i = 1 + a + a^2 + \dots + a^n = \frac{a^{n+1}-1}{a-1} \]
The asymptotic behavior depends on the base \(a\): - If \(\mid a \mid < 1\), the sum converges to a constant as \(n \to \infty\):
\[ \sum_{i=0}^{\infty} a^i = \frac{1}{1-a} \leq C \in \Theta(1). \] This is the “free lunch” of algorithm analysis, showing that the sum of an infinite progression can be bounded by a constant. - If \(a=1\), the sum grows linearly with \(n\): \[ \sum_{i=0}^{n} 1^i = n+1 \in \Theta(n) \] - If \(a>1\), the sum grows exponentially with \(n\): \[ \sum_{i=0}^{n} a^i = \frac{a^{n+1}-1}{a-1} \in \Theta(a^n) \]
The sum of reciprocal integers, which characterizes search patterns in randomized algorithms:
\[ H(n) = \sum_{i=1}^{n} \frac{1}{i} = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \in \Theta(\log n) \]