Master method applies (Yes/No)? If no, then why not? If yes: Two expressions com
ID: 3700549 • Letter: M
Question
Master method applies (Yes/No)? If no, then why not? If yes: Two expressions compared to determine whether it applies (give specific values using the above recurrence, not simply a copy of the Master Method definition): and If Case 1 or Case 3, supply a value of e that verifies a polynomial gap between these expressions Asymptotic complexity of recurrence Which takes asymptotically longer to execute: the work done at the root-node level of the recurrence, the work done by all other levels combined, or neither? d) T(n) = 5T(n/4) + n Master method applies (Yes/No)? If no, then why not? If yes: Two expressions compared to determine whether it applies (give specific values using the above recurrence, not simply a copy of the Master Method definition): and If Case 1 or Case 3, supply a value of e that verifies a polynomial gap between these expressions Asymptotic complexity of recurrence Which takes asymptotically longer to execute: the work done at the root-node level of the recurrence, the work done by all other levels combined, or neither?Explanation / Answer
There are following three cases:
1. If f(n) = ?(nc) where c < Logba then T(n) = ?(nLogba)
2. If f(n) = ?(nc) where c = Logba then T(n) = ?(ncLog n)
3.If f(n) = ?(nc) where c > Logba then T(n) = ?(f(n))
In recurrence tree, if the work done by leaves is more then the root then case 1 is applied. If work done is same at root and work done by leaves then we multiply hight of tree with work done at any level as in case 2. if work done at root is more then case 3 is applied.
C) Yes mater's theorem applies
Two expressions compared c which is 2 (n2) and logba which is again 2 (log39).
case 2 is applied.
Time complexity is O(n2log n).
work done by other levels combined is more.
D) Yes mater's theorem applies
Two expressions compared c which is 1(n1) and logba which is more than 1 (log45).
case 1 is applied.
complexity O(nlog45).
work done by all other levels combined is longer.