in Algorithms
1 flag 1,338 views
1 vote
1 vote
T(n) = T(n/4) + T(3n/4) + n

How to solve these type of problems?

Can I solve this using master theorm by considering X = T(3N/4) +N THEN

T(N) = T(N/4) +X

CAN WE SOLVE LIKE THIS?

PLEASE HELP
  • 🚩 Duplicate | 👮 Hira Thakur | 💬 “https://gateoverflow.in/191487/t-n-t-n-4-t-3n-4-n”
in Algorithms
1 flag
1.3k views

4 Comments

you can use that also but it will give Ω(nlog3n).. because the length of chain will be small as compared to T(2n/3)
0
0

@arvin @Nandkishor3939 

how you guys are calculating T(1)?

please tell in detail ..I'm not able to understand

0
0
If you solve the rec reln by traditional method(by substitution and not by tree method)

you will see that T(n/(3/2)) will be like T(n/(3/2)^k)  for k th transaction ....

so substitute T(1)=T(n/(3/2)^k) because we need to kind value of k such that we will reach the last stage of recurrence relation i.e. T(1)

 

thus we will get an idea of how deep the tree(it is quite intuitive !) will be (that's what the discussion was all about)
0
0

1 Answer

1 vote
1 vote
Solve it by making recurrence tree