Study Notes: Analysis of Algorithms and Asymptotic Analysis

Introduction to Analysis of Algorithms and Asymptotic Analysis

• An algorithm is a finite set of precise instructions for performing a computation or solving a problem.
• Goal of analysis of algorithms: compare algorithms mainly in terms of running time, but also consider memory requirements, programmer's effort, etc.
• Running time analysis: determine how running time grows as the problem size increases.

Input Size

• Input size definitions vary by problem domain:
  • size of an array
  • polynomial degree (in algorithms with polynomial expressions)
  • # of elements in a matrix
  • # of bits in the binary representation of the input
  • vertices and edges in a graph

Types of Analysis

• Worst case: provides an upper bound on running time; an absolute guarantee that the algorithm would not run longer, regardless of input.
• Best case: provides a lower bound on running time; the input for which the algorithm runs fastest.
• Average case: provides a prediction about running time; assumes inputs are random.
• Relationships among bounds:
  • Lower Bound ≤ Running Time ≤ Upper Bound

How do we compare algorithms?

• We need objective measures. Common considerations:
  • Compare execution times: not ideal since times depend on the machine.
  • Count the number of statements executed: not ideal since counts vary with language and programmer style.

Ideal Solution

• Express running time as a function of input size n: f(n).
• Compare different functions corresponding to running times.
• This analysis is machine- and language-independent, focusing on growth rates rather than absolute times.

Example: Cost Model (Algorithm 1 and Algorithm 2)

• We can associate a cost with each statement and total cost by counting how many times each statement executes.
• Algorithm 1 and 2 (illustrative cost model):
  • arr[0] = 0; cost = c1
  • for (i = 0; i < N; i++): cost increment c2 per iteration
  • arr[1] = 0; cost increment c1
  • arr[i] = 0; cost increment c1
  • arr[2] = 0; cost increment c1
  • … arr[N-1] = 0; cost increment c1
• Total costs (illustrative):
  • Algorithm 1: c1 × N + c2 × (N+1) = (c1 + c2) × N + c2
  • Algorithm 2: similar form; total cost shown as (c2 + c1) × N + c2
• Conclusion: Both algorithms are of the same order, O(N).

Example: Algorithm 3 cost

• cost model components: sum = 0; c1
• Nested loops: for i = 0 to N-1; for j = 0 to N-1; sum += arr[i][j];
• Total cost: c1 + c2 × (N+1) + c2 × N × (N+1) + c3 × N^2 = O(N^2)

Asymptotic Analysis

• When comparing two running times f(n) and g(n), we use a rough measure that captures how fast each grows.
• Approach: compare functions in the limit, i.e., asymptotically for large n.

Rate of Growth (intuitive idea)

• Example: buying elephants and goldfish
  • Cost = costofelephants + costofgoldfish
  • Cost ≈ costofelephants for large n (dominant term)
• For a polynomial example, n^4 + 100n^2 + 10n + 50 ~ n^4 as n → ∞; low-order terms become insignificant for large n.
• Therefore, n^4 + 100n^2 + 10n + 50 and n^4 have the same rate of growth.

Asymptotic Notation

• O-notation (Big-O): asymptotic upper bound
  • f(n) = O(g(n)) means: there exist constants c > 0 and n0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0.
• Ω-notation (Big-Omega): asymptotic lower bound
  • f(n) = Ω(g(n)) means: there exist constants c > 0 and n0 such that f(n) ≥ c·g(n) for all n ≥ n0.
• Θ-notation (Big-Theta): asymptotic tight bound
  • f(n) = Θ(g(n)) means: f(n) = O(g(n)) and f(n) = Ω(g(n))

Big-O Notation examples

• f(n) = 30n + 8 is O(n)
• f(n) = n^2 + 1 is O(n^2)
• Any O(n^2) function grows faster than any O(n) function.

Visualizing Orders of Growth

• On a graph, as n increases, faster-growing functions eventually dominate slower ones.
• Example: fA(n) = 30n + 8 is eventually dominated by fB(n) = n^2 as n grows large.

More Examples of Orders

• n^4 + 100n^2 + 10n + 50 is O(n^4)
• 10n^3 + 2n^2 is O(n^3)
• n^3 − n^2 is O(n^3)
• Constants are O(1)
• 10 is O(1) and 1273 is O(1)

Back to Our Example (Algorithm Cost)

• Algorithm 1 and Algorithm 2: cost is O(N) (linear)
• Algorithm 3: cost is O(N^2) (quadratic)

Asymptotic Notations (formal definitions)

• O-notation (formal):
  • O(g(n)) = { f(n) : there exist positive constants c and n0 such that 0 ≤ f(n) ≤ c g(n) for all n ≥ n0 }
• Big-Omega:
  • Ω(g(n)) = { f(n) : there exist positive constants c and n0 such that f(n) ≥ c g(n) for all n ≥ n0 }
• Theta:
  • Θ(g(n)) = { f(n) : f(n) ∈ O(g(n)) and f(n) ∈ Ω(g(n)) }

Big-O Visualization (set perspective)

• The set of functions with growth at most that of g(n) is O(g(n)).
• Θ(g(n)) is the intersection of O(g(n)) and Ω(g(n)).

Examples – Two Relationships (quick look)

• n^2 = Ω(n) but not O(n^2) in the sense of strictness; more precise statements follow from definitions.
• n = Θ(n) is trivial; constant factors do not matter in Θ.
• log n and log log n have different growth rates: log log n = o(log n) (and thus O(log n) but not Ω(log n)).

Relationships Between Different Sets

• Subset relations: O(f) ⊆ Θ(f) ⊆ Ω(f) in appropriate contexts, but more precisely:
  • Θ(f) ⊆ O(f) and Θ(f) ⊆ Ω(f)

Common Orders of Magnitude (typical growth rates)

• Constant: Θ(1)
• Logarithmic: Θ(log n)
• Linear: Θ(n)
• Linearithmic: Θ(n log n)
• Polynomial: Θ(n^k) for k ≥ 2
• Exponential: Θ(2^n)
• Factorial: Θ(n!)
• (These illustrate a sense of relative growth; exact tables show concrete values for specific n, but growth ordering remains as listed.)

Common Summations (useful in algorithm analysis)

• Arithmetic series:

  • 
    
    \,\sum_{k=1}^{n} k = \frac{n(n+1)}{2}
    

• Geometric series (finite):

  • If x ≠ 1,
    
    \,\sum_{k=0}^{n} x^{k} = \frac{1 - x^{n+1}}{1 - x}
    
  • Infinite sum for |x| < 1:
    \sum_{k=0}^{\infty} x^{k} = \frac{1}{1 - x}
    

• Harmonic series:
  \sum{k=1}^{n} \frac{1}{k} = Hn \approx \ln n + \gamma\quad (\gamma\text{ is the Euler–Mascheroni constant})

• Additional typical approximations:

  • \sum_{k=1}^{n} k^p \sim \frac{n^{p+1}}{p+1} \quad\text{for large } n,\text{ when } p > -1
  • \sum_{k=1}^{n} \log k \approx n\log n - n (Stirling-type intuition)

Mathematical Induction

• A powerful, rigorous technique to prove a statement S(n) holds for every natural number n.
• Proof structure:
  • Basis step: prove S(n) for the initial value (often n = 1).
  • Inductive step: assume S(n) true for some n ≥ n0; prove S(n+1) true for all such n.
• Core idea: show that if the statement holds for one case, it holds for the next, propagating truth.

Example (useful induction pattern)

• Statement: Prove that 2^n ≥ n^2 for all n ≥ 4.
  • Basis: n = 4 → 2^4 = 16 ≥ 4^2 = 16 (true).
  • Inductive step: assume 2^n ≥ n^2 for some n ≥ 4. Then
    2^{n+1} = 2\cdot 2^n ≥ 2\cdot n^2.
    To conclude 2^{n+1} ≥ (n+1)^2, we require 2n^2 ≥ (n+1)^2, i.e., n^2 ≥ 2n + 1, which holds for n ≥ 3. Since n ≥ 4 in the inductive step, the inequality holds.
• Therefore, by induction, 2^n ≥ n^2 for all n ≥ 4.

Logarithms and properties

• Change of base:
  \log_b x = \frac{\ln x}{\ln b}
• Basic properties:
  • \log(x^k) = k\log x
  • \log(xy) = \log x + \log y
  • Base changes and relationships among bases yield constant factors, which are absorbed in Θ-notations.
• Common bases: binary (log base 2), natural (ln), and base 10; all differ only by constant factors.

Examples – Relationships (quick exercise guidance)

• If f(n) = log n^2 and g(n) = log n + 5:
  • log n^2 = 2 log n, so f(n) = Θ(log n).
  • log n + 5 = Θ(log n).
  • Therefore, f(n) = Θ(g(n)).
• If f(n) = n and g(n) = log n^2:
  • n grows faster than log n^2, so f(n) = Ω(g(n)) (and not O(g(n))).
• If f(n) = log log n and g(n) = log n:
  • log log n = o(log n) ⇒ f(n) = O(g(n)) and f(n) ≠ Ω(g(n)).
• If f(n) = n and g(n) = log n:
  • f(n) = Ω(g(n)) (and not O(g(n))).
• If f(n) = n log n + n and g(n) = log n:
  • f(n) = Ω(g(n)) (grows faster than log n).
• If f(n) = 10 and g(n) = log 10:
  • Both are constants; f(n) = Θ(g(n)).

Properties of Asymptotic Notations (summary)

• Theorem: f(n) = Θ(g(n)) ⇔ f(n) = O(g(n)) and f(n) = Ω(g(n)).
• Transitivity:
  • If f(n) = Θ(g(n)) and g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n)).
  • Similar transitivity holds for O and Ω with corresponding relations.
• Reflexivity:
  • f(n) = Θ(f(n)); f(n) = O(f(n)); f(n) = Ω(f(n)).
• Symmetry:
  • f(n) = Θ(g(n)) ⇔ g(n) = Θ(f(n)).
• Transpose symmetry:
  • f(n) = O(g(n)) ⇔ g(n) = Ω(f(n)).

Asymptotic Notations in Equations

• If the right-hand side uses Θ(g(n)) as a placeholder for an unknown function, it expresses that the left-hand side equals the right-hand side up to a function in Θ(g(n)).
• Conversely, the left-hand side can be written as Θ(n^2) by choosing an appropriate anonymous function on the right-hand side to make the equality valid.

Common Orders of Magnitude (quick reference)

• Constant: Θ(1)
• Logarithmic: Θ(log n)
• Linear: Θ(n)
• Linearithmic: Θ(n log n)
• Polynomial: Θ(n^k) for k ≥ 2
• Exponential: Θ(2^n)
• Factorial: Θ(n!)

Common Summations (recap)

• Arithmetic series:
  \sum_{k=1}^{n} k = \frac{n(n+1)}{2}
• Geometric series: finite and infinite forms as above.
• Harmonic series:
  \sum{k=1}^{n} \frac{1}{k} = Hn \approx \ln n + \gamma

Summary: Structure of Study Notes

• Key concepts: definitions of input size, cost model, types of analysis, and growth rates.
• Core tools: Big-O, Big-Ω, Big-Θ, and their properties.
• Techniques: rate-of-growth reasoning, limit behavior, and induction.
• Examples: linear vs quadratic time, simple summations, and induction proofs.
• Connections to real-world relevance: choosing efficient algorithms based on input size and growth behavior, not just constant-time measurements.

Note

• The transcript includes a few typographical inconsistencies in the induction example. The essential induction framework is valid: basis, inductive step, and conclusion. A common robust example is proving that a ∈Θ(b) by showing both O- and Ω-bounds via fixed constants after appropriate n0. When practicing, prefer standard, well-checked inequalities (e.g., 2^n ≥ n^2 for n ≥ 4) to avoid edge-case ambiguities.