🔢Analytic Number Theory Unit 3 – Asymptotic Notation and Summations

Key Concepts and Definitions

• Asymptotic notation describes the behavior of functions as their input grows arbitrarily large
• Big O notation ($O(f(n))$) represents an upper bound on the growth rate of a function
  • Formally, $f(n) = O(g(n))$ if there exist constants $c > 0$ and $n_0$ such that $|f(n)| \leq c|g(n)|$ for all $n \geq n_0$
• Big Omega notation ($\Omega(f(n))$) represents a lower bound on the growth rate of a function
  • Formally, $f(n) = \Omega(g(n))$ if there exist constants $c > 0$ and $n_0$ such that $|f(n)| \geq c|g(n)|$ for all $n \geq n_0$
• Big Theta notation ($\Theta(f(n))$) represents a tight bound on the growth rate of a function
  • Formally, $f(n) = \Theta(g(n))$ if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$
• Little o notation ($o(f(n))$) represents a strict upper bound on the growth rate of a function
  • Formally, $f(n) = o(g(n))$ if for any constant $c > 0$, there exists a constant $n_0$ such that $|f(n)| < c|g(n)|$ for all $n \geq n_0$
• Little omega notation ($\omega(f(n))$) represents a strict lower bound on the growth rate of a function
  • Formally, $f(n) = \omega(g(n))$ if for any constant $c > 0$, there exists a constant $n_0$ such that $|f(n)| > c|g(n)|$ for all $n \geq n_0$

Types of Asymptotic Notation

• Big O notation is the most commonly used asymptotic notation
  • Provides an upper bound on the growth rate of a function
  • Useful for analyzing worst-case time complexity of algorithms ($O(n^2)$ for bubble sort)
• Big Omega notation is used to describe lower bounds on the growth rate of a function
  • Useful for analyzing best-case time complexity of algorithms ($\Omega(n)$ for linear search)
• Big Theta notation is used when a function is bounded both above and below by the same growth rate
  • Describes the average-case time complexity of algorithms ($\Theta(n \log n)$ for merge sort)
• Little o notation is a strict upper bound, meaning the function grows slower than the bounding function
  • Useful for describing the relative growth rates of functions ($n = o(n^2)$)
• Little omega notation is a strict lower bound, meaning the function grows faster than the bounding function
  • Useful for describing the relative growth rates of functions ($n^2 = \omega(n)$)

Properties of Asymptotic Notation

• Transitivity: If $f(n) = O(g(n))$ and $g(n) = O(h(n))$, then $f(n) = O(h(n))$
• Reflexivity: $f(n) = O(f(n))$ for any function $f(n)$
• Symmetry: $f(n) = \Theta(g(n))$ if and only if $g(n) = \Theta(f(n))$
• Addition: If $f(n) = O(h(n))$ and $g(n) = O(h(n))$, then $f(n) + g(n) = O(h(n))$
  • Example: $n^2 + n = O(n^2)$
• Multiplication by a constant: If $f(n) = O(g(n))$, then $kf(n) = O(g(n))$ for any constant $k > 0$
  • Example: $5n^2 = O(n^2)$
• Multiplication: If $f(n) = O(h(n))$ and $g(n) = O(p(n))$, then $f(n)g(n) = O(h(n)p(n))$
  • Example: $n \cdot \log n = O(n \log n)$

Summation Techniques and Formulas

• Arithmetic series: $\sum_{i=1}^{n} i = \frac{n(n+1)}{2} = O(n^2)$
• Geometric series: $\sum_{i=0}^{n} ar^i = \frac{a(1-r^{n+1})}{1-r}$ for $r \neq 1$
  • If $|r| < 1$, the series converges to $\frac{a}{1-r}$ as $n \to \infty$
• Harmonic series: $\sum_{i=1}^{n} \frac{1}{i} = \ln n + O(1)$
• Telescoping series: Useful for simplifying summations by canceling out terms
  • Example: $\sum_{i=1}^{n} (f(i) - f(i-1)) = f(n) - f(0)$
• Summation by parts: A technique for rewriting summations using partial summation
  • Analogous to integration by parts
  • $\sum_{i=1}^{n} a_i b_i = A_n b_n - \sum_{i=1}^{n-1} A_i (b_{i+1} - b_i)$, where $A_i = \sum_{j=1}^{i} a_j$

Applications in Number Theory

• Estimating the growth of arithmetic functions, such as the divisor function $d(n)$ or the sum of divisors function $\sigma(n)$
  • Example: $\sum_{n=1}^{x} d(n) = x \log x + (2\gamma - 1)x + O(\sqrt{x})$, where $\gamma$ is the Euler-Mascheroni constant
• Analyzing the complexity of number-theoretic algorithms, such as the Euclidean algorithm for finding the greatest common divisor (GCD)
  • The Euclidean algorithm has a worst-case time complexity of $O(\log \min(a, b))$ for input integers $a$ and $b$
• Studying the distribution of prime numbers using the Prime Number Theorem
  • The Prime Number Theorem states that the number of primes less than or equal to $x$, denoted by $\pi(x)$, is asymptotically equal to $\frac{x}{\ln x}$
  • Formally, $\lim_{x \to \infty} \frac{\pi(x)}{x / \ln x} = 1$ or $\pi(x) \sim \frac{x}{\ln x}$
• Investigating the average-case behavior of arithmetic functions using asymptotic density
  • Example: The asymptotic density of square-free integers is $\frac{6}{\pi^2}$, meaning that the proportion of square-free integers among all positive integers tends to $\frac{6}{\pi^2}$ as the number of integers considered grows arbitrarily large

Common Pitfalls and Misconceptions

• Confusing the different types of asymptotic notation and their meanings
  • Big O, Big Omega, and Big Theta are not interchangeable and describe different aspects of a function's growth
• Misinterpreting the role of constants in asymptotic notation
  • Constants are ignored in asymptotic notation, so $f(n) = O(g(n))$ does not imply $f(n) \leq g(n)$ for all $n$
• Incorrectly applying asymptotic notation to functions with multiple variables
  • When using asymptotic notation for functions with multiple variables, it is essential to specify which variable is growing arbitrarily large
• Misunderstanding the limitations of asymptotic analysis
  • Asymptotic notation describes the behavior of functions for sufficiently large input sizes and may not accurately reflect the performance for small inputs
• Overlooking the importance of lower-order terms in practical applications
  • While lower-order terms are ignored in asymptotic notation, they can significantly impact the actual running time of algorithms for moderate input sizes

Practice Problems and Examples

• Prove that $2^n = O(3^n)$
  • Solution: Let $c = 1$ and $n_0 = 0$. For all $n \geq n_0$, we have $2^n \leq 1 \cdot 3^n$, so $2^n = O(3^n)$
• Show that $\log_2 n = \Theta(\log_3 n)$
  • Solution: Using the change of base formula, $\log_2 n = \frac{\log_3 n}{\log_3 2}$. Since $\log_3 2$ is a constant, $\log_2 n = \Theta(\log_3 n)$
• Prove that $\sum_{i=1}^{n} i^2 = \Theta(n^3)$
  • Solution: Using the formula for the sum of squares, $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$. As $n \to \infty$, the dominant term is $\frac{n^3}{3}$, so $\sum_{i=1}^{n} i^2 = \Theta(n^3)$
• Analyze the time complexity of the following algorithm for computing the sum of the first $n$ cubes:

def sum_of_cubes(n):
    result = 0
    for i in range(1, n+1):
        result += i**3
    return result

• Solution: The algorithm uses a single loop that iterates $n$ times, and each iteration performs a constant number of operations. Therefore, the time complexity is $O(n)$

Advanced Topics and Extensions

• Asymptotic notation for multiple variables, such as $O(mn)$ for matrix multiplication
• Adaptive analysis, which considers the performance of algorithms on inputs with specific properties
  • Example: The adaptive time complexity of the Euclidean algorithm is $O(\log \min(a, b))$ for inputs $a$ and $b$, but it can be as low as $O(\log \log \min(a, b))$ for inputs that satisfy certain conditions
• Smoothed analysis, which studies the expected performance of algorithms under slight perturbations of worst-case inputs
  • Helps explain the discrepancy between the theoretical worst-case complexity and the observed average-case performance of some algorithms
• Amortized analysis, which considers the average performance of a sequence of operations
  • Useful for analyzing data structures with occasional expensive operations, such as dynamic arrays (vectors) with doubling capacity
• Probabilistic analysis, which studies the expected performance of randomized algorithms
  • Example: The expected time complexity of the randomized quicksort algorithm is $O(n \log n)$, despite having a worst-case complexity of $O(n^2)$
• Applying asymptotic notation to the analysis of space complexity and memory usage of algorithms
  • Helps understand the trade-offs between time and space complexity in algorithm design