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

Question

How to solve above recurrence relation (With substitution method)??

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

answer Wii be  O(n log_4/3 n) using recursive tree method. 

Comments

 i hope it will be help you

 https://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html

---

air1ankit

u missed Big O notation.

---

As in binary tree we go down from 1st level. we divide n into 2 parts then further 2 parts and we keep doing till we reach leaves and that's where height becomes log n base 2. same way here we divide by 3/4 at each level and so it becomes log n base 4/3.

Answer 2

$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?