1 votes 1 votes 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 Algorithms recurrence-relation time-complexity algorithms + โ ๐ฉ Duplicate | ๐ฎ Hira Thakur | ๐ฌ โhttps://gateoverflow.in/191487/t-n-t-n-4-t-3n-4-nโ Mayankprakash asked Jan 4, 2019 Mayankprakash 1.3k views answer comment Share Follow See all 13 Comments See all 13 13 Comments reply Mayankprakash commented Jan 4, 2019 reply Follow Share @Shaik Masthan @arvin please help me on this 0 votes 0 votes arvin commented Jan 4, 2019 reply Follow Share 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 votes 0 votes Mayankprakash commented Jan 4, 2019 reply Follow Share @arvin Then how do we tackle these type of problems? can you please provide easy way to solve these Thanks โโ 0 votes 0 votes Deepanshu commented Jan 4, 2019 i edited by Deepanshu Jan 5, 2019 reply Follow Share 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 votes 0 votes Hemanth_13 commented Jan 4, 2019 reply Follow Share For this case the TC = $\theta(n)$ It will same TC if we take best case and worst case 0 votes 0 votes arvin commented Jan 5, 2019 reply Follow Share 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 1 votes 1 votes arvin commented Jan 5, 2019 reply Follow Share @Hemanth_13 it will be nlogn(approx) why n? check once 0 votes 0 votes Nandkishor3939 commented Jan 5, 2019 reply Follow Share 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 votes 0 votes arvin commented Jan 5, 2019 reply Follow Share @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 votes 0 votes Nandkishor3939 commented Jan 5, 2019 reply Follow Share @arvin why not T(1)=T(n/(3)^k) 0 votes 0 votes arvin commented Jan 6, 2019 reply Follow Share 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 votes 0 votes Mayankprakash commented Jan 7, 2019 reply Follow Share @arvin @Nandkishor3939 how you guys are calculating T(1)? please tell in detail ..I'm not able to understand 0 votes 0 votes Nandkishor3939 commented Jan 7, 2019 reply Follow Share 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 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Solve it by making recurrence tree vikash_thakur answered Jun 15, 2019 vikash_thakur comment Share Follow See all 0 reply Please log in or register to add a comment.