Algorithm Analysis

CREATED: 200701150332

QuickSort Analysis

Summation

• Trivial upper bound, assume all terms as large as the largest term
• Trivial lower bound, sum the upper/larger half of the terms, assume all terms as large as the smallest term
• Integration bounds over the bar graph
• Taylor’s Theorem
• Convert product to summation using log
• Summation of finite number of positive terms can be bounded by summation to infinity

Recurrences

• Guess and verify
  • strengthen the induction
• Plug and chug
• Linear homogeneous
  • form the characteristic equation (CE)
  • if r is a non-repeated root of CE, then \(r^n\) is a solution
  • if r is a repeated root with multiplicity k then \(r^n, nr^n, \ldots, n^{k-1}r^n\) are all solutions to the recurrence
  • Linear combination of solutions are also solutions
• Linear inhomogeneous
  • solve the homogeneous recurrence
  • find a particular solution
    • look for same form as g(n)
    • if g(n) is a constant, try \(f(n) = c, f(n) = bn + c, f(n) = an^2 + bn + c\)
    • if g(n) is a polynomial, try same degree, one degree higher, etc
    • if g(n) is exponential, such as \(3^n\), try \(f(n) = c3^n, f(n) = bn3^n + c3^n, f(n) = an^2 3^n + bn3^n + c3^n\)
  • add solutions and find constants

Master’s theorem

• Applies to recurrences of the following form:
• \(T(n) = aT(n/b) + f(n)\) where \(a \ge 1, b > 1\) and \(f(n)\) is an asymptotically positive function.
• If \(f(n) = O(n^{\log_b a - \epsilon})\) for some constant \(\epsilon > 0\) then \(T(n) = \Theta(n^{\log_b a})\)
• If \(f(n) = \Theta(n^{\log_b a} log^k n)\) with \(k \ge 0\) then \(T(n) = \Theta(n^{\log_b a}\log^{k+1} n)\)
• If \(f(n) = \Omega(n^{\log_b a + \epsilon})\) with \(\epsilon > 0\) and \(f(n)\) satisfies the regularity condition then \(T(n) = \Theta(f(n))\)
  • Regularity condition: \(af(n/b) \le cf(n)\) for some constant \(c < 1\) for all sufficiently large \(n\)

Akra-Bazzi Method