Question

. Consider the recurrence T(n) = 2n + T(bn/4c) + T(b(3/4)nc), where T(n) = 1 if n < 10. Prove by induction that T(n) = O(n log n). g

Answer 1

Step-by-step explanation:

$T(n) = T(\frac{n}{4})+T(\frac{3n}{4})+2n \ \ \; \ n > 10$

$T(n) = 0; \ \ n<0$

Therefore,

$T(n)= T(\frac{n}{4})+T(\frac{3n}{4})+2n$

$T(\frac{n}{4})= T(\frac{n}{16})+T(\frac{3n}{16})+(\frac{2n}{4}) \ \ ...(i)$

$T(\frac{3n}{4})= T(\frac{3n}{16})+T(\frac{9n}{16})+(\frac{6n}{4}) \ \ ...(ii)$

$\Rightarrow \frac{n+3n+3n+9n}{16} = \frac{16n}{16}$

                                = n

$\therefore n+n+n+.... = n \cdot \log_{\frac{4}{3}}n$

$\therefore T(n) = n \cdot \log_{\frac{4}{3}}n$