#Recurrence_Relation

Question

How to solve this in the simplest way?

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

Comments

(3/4)^k n = 1  by assuming T(1) =1

n = (4/3)^k

log_4/3n = k

So, total cost = n+n+n+...(k+1) times

So, total cost = n*(k+1) = n*(log_4/3n+1) = O(n*log_4/3n)

---

Thanks :)

---

Thanks both of u :)

Answer 1

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

$a_{1} = 1 , a_{2} = 1$

$b_{1} = 1/4 , b_{2} = 3/4$

$g(n) = n$

$g(u) = u$

$(1/4)^p + (3/4)^p = 1$

when $p = 1, LHS = RHS$

This method gives $T(x) \epsilon \Theta(f(x))$

$f(x) = x^p.( 1 + \int_{1}^{x} g(u)/u^{p+1} )$

        $= x.( 1 + \int_{1}^{x} u/u^{2} )$                                        

        $= x.( 1 + \int_{1}^{x} 1/u )$

        $= x.( 1 + log x )$

$T(n) = \Theta(nlogn)$ , on replacing $x$ witn $n$

1. https://www.youtube.com/watch?v=Gl2v9G0Rn4k

Comments

still not able to understand ....can you tell any other method @pankaj_vir?

---

Which are you are not able to understand, tell me?