0 votes 0 votes Can we solve it by master Theorem T(n)=T(n/3)+T(n/4)+6n Algorithms time-complexity + – bhavnakumrawat5 asked Jul 18, 2018 bhavnakumrawat5 400 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Naveen Kumar 3 commented Jul 18, 2018 reply Follow Share T(n)={T(n/3)+3n}+{T(n/4)+3n} applicable! yes? 1 votes 1 votes air1ankit commented Jul 18, 2018 reply Follow Share I think we can apply master method when it is in T(n) = aT(n/b) + f(n) this form .. 1 votes 1 votes Priyanka Agarwal commented Jul 19, 2018 reply Follow Share How it is applicable 0 votes 0 votes Priyanka Agarwal commented Jul 19, 2018 reply Follow Share Okkkk got it 0 votes 0 votes harishrajora commented Jul 19, 2018 reply Follow Share Can we go for T(n/3) as T1 and T(n/4)+6n as T2?? 0 votes 0 votes ankitgupta.1729 commented Jul 20, 2018 reply Follow Share T(n)=T(n/3)+3n+T(n/4)+3n can be written as T(n)=T1+T2 where T1=T(n/3)+3n and suppose T2=T(n/4)+3n Solve indvidually both..:) Suppose, T(n) = 2T(n/2) + $\Theta(1)$ if we write T(n) = T1 + T2 where T1 = T2 = T(n/2) + $\Theta(1)$ Now, if we apply Master theorem individually for T(n) , T1 and T2 Then , T(n) and T1 + T2 will give different asymptotic upper bounds. So what you are saying is not correct. 0 votes 0 votes ankitgupta.1729 commented Jul 20, 2018 reply Follow Share Master Theorem is not applicable here. if you recall Master Theorem , then assumption was :- "All subproblems should have equal size" . Here , subproblems don't have equal size. So, Master Theorem is not applicable here. In Master Theorem , For large value of 'n', Recurrence Format is :- T(n) $\leqslant$ aT(n/b) + $\Theta$(nd) , where a,b and d are independent of 'n' and base case :- T(n) <= a constant. Here , a = number of recursive calls ($\geqslant$1) b= input size shrinkage factor (>1) d= exponent in running time of "combine" step. ($\geqslant$0) 0 votes 0 votes Shubham Shukla 6 commented Jul 20, 2018 reply Follow Share yes @ankit we need to use tree method to solve such problems..:) 0 votes 0 votes Please log in or register to add a comment.