Question 1

Consider the following recurrence relation of $T (n)$ :

T (1) = 1, T (n) = T (⌈ \frac{n}{3} ⌉) + 1

Use The Master Theorem to show that $T (n) \in Θ (lo g_{2} n)$ . $a = 1, b = 3, f (n) = 1$ $k = lo g_{3} (1) = 0 ∴ f (n) \in Θ (n^{0}) \equiv Θ (1)$ $T (n) = Θ (n^{k} lo g_{2} n) = Θ (lo g_{2} n)$
Verify lower-bound by showing $T (n) \geq \frac{1}{2} lo g_{2} n$ for all $n \geq 1$ . Base Case: LHS = $T (1) = 1$ , RHS = $\frac{1}{2} lo g_{2} (1) = 0$ Hence, $L H S \geq R H S$ which means the base case holds. Inductive Case: Assume $T (m) \geq \frac{1}{2} lo g_{2} (m)$ for all $m \leq k$ . By definition, $T (k + 1) = T (⌈ \frac{k + 1}{3} ⌉) + 1$ . $T (k + 1) \geq \frac{1}{2} lo g_{2} (⌈ \frac{k + 1}{3} ⌉) + 1 \geq \frac{1}{2} lo g_{2} (\frac{k + 1}{3}) + 1 = \frac{1}{2} [lo g_{2} (k + 1) - lo g_{2} (3)] + 1 = \frac{1}{2} lo g_{2} (k + 1) - \frac{1}{2} lo g_{2} (3) + 1 = \frac{1}{2} lo g_{2} (k + 1) + 0.207 \geq \frac{1}{2} lo g_{2} (k + 1) as required$

Hence this formula holds for all values of $m \le k$. 3. Verify upper-bound by showing $T(n) \le 2 \log_2 n$ for all $n \ge 2$. 4. Why is the upper-bound much harder to prove than the lower-bound? # Question 2 1. Construct recurrence relation $T(n)$ such that: - $T(1) = 1$

Archive Notes