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) = \begin{cases} k & \text{if } n = 1 \ aT(\frac{n}{b}) + n^c & \text{if } n > 1 \end{cases}

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

• Solutions:

  • If \log_b a < c, then T(n) = O(n^c)
  • If \log_b a = c, then T(n) = O(n^c \log n)
  • If \logb a > c, then T(n) = O(n^{\logb a})

• Example:

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

Applying the Master Theorem

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