Mathematical Review

Mathematical Review for Algorithm Analysis

A solid understanding of basic mathematics is essential for analyzing and designing efficient algorithms. Many algorithms—especially in computer science—rely on mathematical concepts such as functions, relations, series, and asymptotic analysis to evaluate their performance and behavior. This review covers the mathematical tools and techniques commonly used in algorithm analysis.

---

1. Functions and Growth Rates

When analyzing an algorithm, the running time (or space usage) is often expressed as a function of the input size. This function describes how the performance of an algorithm changes as the input size increases. For example, if an algorithm takes n steps to process an input of size n, we say that the time complexity of the algorithm is O(n).

Common Growth Functions in Algorithm Analysis:

• Constant Function: $f(n) = c$

  • The time (or space) does not change with the input size.
  • Example: Accessing an element in an array by index takes constant time O(1).

• Linear Function: $f(n) = n$

  • The time (or space) grows linearly with the input size.
  • Example: Iterating over an array or list takes linear time O(n).

• Quadratic Function: $f(n) = n^2$

  • The time grows quadratically with the input size.
  • Example: Bubble sort, which compares each element with every other element.

• Logarithmic Function: $f(n) = \log n$

  • The time grows logarithmically as the input size increases. This is much slower than linear growth and is desirable for algorithms like binary search.

• Linearithmic Function: $f(n) = n \log n$

  • The time grows faster than linear but slower than quadratic. Common in efficient sorting algorithms like merge sort and quick sort.

• Exponential Function: $f(n) = 2^n$

  • The time grows exponentially with the input size. Exponential time complexities are inefficient for large inputs and often occur in problems that require exhaustive searching, like the Traveling Salesman Problem.

• Factorial Function: $f(n) = n!$

  • The time grows factorially. This growth is very fast and impractical for large inputs. Examples include problems that generate permutations of elements.

---

2. Asymptotic Notation

In algorithm analysis, we often use asymptotic notation to describe the growth of functions. This helps us understand how algorithms perform as the input size grows, ignoring constant factors and lower-order terms.

Big-O Notation (O):

• Big-O notation expresses the upper bound of an algorithm's running time. It describes the worst-case growth rate of an algorithm.
  • Definition: A function f(n) is O(g(n)) if there exist constants c and n₀ such that for all n ≥ n₀, $|f(n)| \leq c \cdot g(n)$.
  • Example: If an algorithm has a time complexity of O(n²), it means that for large enough n, the running time will grow at most as fast as n².

Big-Ω Notation (Ω):

• Big-Ω notation expresses the lower bound of an algorithm's running time. It describes the best-case growth rate.
  • Definition: A function f(n) is Ω(g(n)) if there exist constants c and n₀ such that for all n ≥ n₀, $|f(n)| \geq c \cdot g(n)$.
  • Example: An algorithm with Ω(n) time complexity will take at least n operations in the best case.

Big-Θ Notation (Θ):

• Big-Θ notation expresses a tight bound on an algorithm's time complexity. It gives both the upper and lower bounds, meaning the algorithm's performance will grow at the rate of g(n) asymptotically.
  • Definition: A function f(n) is Θ(g(n)) if there exist positive constants c₁, c₂, and n₀ such that for all n ≥ n₀, $c₁ \cdot g(n) \leq f(n) \leq c₂ \cdot g(n)$.
  • Example: If an algorithm's time complexity is Θ(n log n), this means that the running time grows asymptotically at the rate of n log n.

---

3. Summations and Series

In many algorithms, especially those involving loops or recursive functions, we need to sum up operations performed at different stages of execution. Summations are used to express the total number of operations across different iterations or recursive calls.

Arithmetic Series:

An arithmetic series has the form:
$1 + 2 + 3 + \dots + n$
The sum of the first n integers is given by: $\sum_{i=1}^{n} i = \frac{n(n + 1)}{2} = O(n^2)$ This is often seen in algorithms with nested loops.

Geometric Series:

A geometric series has the form:
$1 + r + r^2 + r^3 + \dots + r^n$
The sum of the first n terms of a geometric series is: $\sum_{i=0}^{n} r^i = \frac{1 - r^{n+1}}{1 - r}$ For r = 2, this is the series often found in divide-and-conquer algorithms like binary search or merge sort, where the problem size is halved at each step. The sum of operations in such cases grows logarithmically: O(log n).

Sum of Logarithms:

The sum of logarithms is also frequently encountered in algorithm analysis, especially when dealing with recursion or divide-and-conquer problems. $\sum_{i=1}^{n} \log i = O(n \log n)$

---

4. Recurrences and Solving Recurrence Relations

Recurrences are equations that define a function in terms of itself. They are often used to describe the time complexity of recursive algorithms.

Example Recurrence Relation:

Consider the recurrence for Merge Sort: $T(n) = 2T(n/2) + O(n)$ This states that to solve a problem of size n, we solve two subproblems of size n/2 (the 2T(n/2) term), and then we combine the results in O(n) time.

We can solve such recurrences using various methods:

• Substitution Method: We guess the solution and then prove it by induction.
• Master Theorem: A formula that can be applied directly to solve recurrences of the form: $T(n) = aT(n/b) + O(n^d)$

For Merge Sort, we have:

• a = 2, b = 2, d = 1 (since merging takes linear time).
• Using the Master Theorem, we find that the time complexity is O(n log n).

---

5. Logarithms and Their Properties

Logarithms are crucial in analyzing algorithms that divide a problem in half at each step, such as binary search and divide-and-conquer algorithms. Some important properties of logarithms include:

• Logarithmic Identity: $\log_b x = \frac{\log_a x}{\log_a b}$
• Logarithmic Base Change: $\log_b x = O$log x) $$ for any constant base b (because logarithms with different bases differ only by a constant factor).

In algorithm analysis, we often drop the base of the logarithm and simply write O(log n), as the base does not affect the asymptotic growth.

---

6. Probability and Randomized Algorithms

Some algorithms, especially randomized algorithms, have performance that depends on probability. The analysis of such algorithms uses probability theory to calculate the expected time complexity (average case). A randomized algorithm might use randomness to make decisions during execution, and its performance can vary on each run. Expected time complexity is the average time an algorithm takes over all possible inputs.

For example, in a randomized quicksort, the choice of pivot is random, and its average case time complexity is O(n log n), although the worst-case time complexity (if the pivot choice is bad) could be O(n²).

---

Conclusion

Mathematical concepts are foundational to the design and analysis of algorithms. Whether it's understanding growth rates, using asymptotic notation, solving recurrences, or working with summations and series, mathematical tools provide a structured way to evaluate and optimize algorithms. A solid grasp of these concepts is key to understanding how algorithms scale with input size, which ultimately leads to choosing the right algorithm for a given problem.