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

Explanation:

`$ T(n) = T((n)/(4))+T((3n)/(4))+2n \ \ \; \ n > 10 $`

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

Therefore,

`$ T(n)= T((n)/(4))+T((3n)/(4))+2n $`

`$ T((n)/(4))= T((n)/(16))+T((3n)/(16))+((2n)/(4)) \ \ ...(i)$`

`$ T((3n)/(4))= T((3n)/(16))+T((9n)/(16))+((6n)/(4)) \ \ ...(ii)$`

`$ \Rightarrow (n+3n+3n+9n)/(16) = (16n)/(16)$`

= n

`$ \therefore n+n+n+.... = n \cdot \log_{(4)/(3)}n$`

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