The Gateway to Computer Science Excellence
0 votes
192 views
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
in Algorithms by Junior (997 points) | 192 views
0

@Shaik Masthan @arvin

please help me on this

0
no brother you have to consider both the function to get the result though only one side can be considered either to find best case time or worst case time.
0

@arvin 

Then how do we tackle these type of problems?

can you please provide easy way to solve these

Thanks

​​

0
bro see which one is big and we merge smaller one into it means we ignore it simply......

T(n) = T( 3n/4) + n
0
For this case the TC = $\theta(n)$

It will same TC if we take best case and worst case
+1

brother use recursive tree method when there is more than one function...

and go with basics it will help you to reduce it to simple methods.

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

0

@Hemanth_13 it will be nlogn(approx) why n? check once

0

Hey @arvin , in the second example of the below site (T(n) = T(n/3) + T(2n/3) + n.)

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

how we came to know that size of the tree is log3/2 n ??

 

0

@Nandkishor3939 till T(1)=T(n/(3/2)^k) means n/(3/2)^k= 1 simplify this and you will get k = log(3/2)n and it will be the longest path and n/(3)^k will be the shortest path k= log3n...

0

@arvin why not T(1)=T(n/(3)^k)

0
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

@arvin @Nandkishor3939 

how you guys are calculating T(1)?

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

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)

1 Answer

+1 vote
Solve it by making recurrence tree
by (93 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,601 answers
195,849 comments
102,208 users