Algorithm Analysis and the Master Theorem

Design a Bad Sort Algorithm

  • Goal: Design an inefficient sorting algorithm.
  • Consideration: Time complexity.

The Master Theorem

  • Used to determine the time complexity of algorithms with specific recurrence relations.

  • General form:

    T(n)={kif n=1 aT(nb)+ncif n>1T(n) = \begin{cases} k & \text{if } n = 1 \ aT(\frac{n}{b}) + n^c & \text{if } n > 1 \end{cases}

    where a>0a > 0, b>1b > 1, c≥0c \ge 0, d≥0d \ge 0, k>0k > 0

  • Solutions:

    • If log⁡ba<c\log_b a < c, then T(n)=O(nc)T(n) = O(n^c)
    • If log⁡ba=c\log_b a = c, then T(n)=O(nclog⁡n)T(n) = O(n^c \log n)
    • If log⁡<em>ba>c\log<em>b a > c, then T(n)=O(nlog⁡</em>ba)T(n) = O(n^{\log</em>b a})

  • Example:

    • Given solution: T(n)=O(nlog⁡n)T(n) = O(n \log n)
    • Which can also be expressed as: O(nlog⁡ba)O(n \log_b a)

Applying the Master Theorem

  • Objective: Use the master theorem to determine the time complexity of algorithms from recurrence relations.