For each recurrence, complete the table by using Master Theorem Case 2. 1. T(n)
ID: 3633788 • Letter: F
Question
For each recurrence, complete the table by using Master Theorem Case 2.
1. T(n) = T(n/10) + 10^5
2. T(n) = 3T(n/9) + vn/100
3. T(n) = 8T(n/8) + 8n
4. T(n) = 8T(n/2) + ?(n3)
a =
b=
Number of subproblems =
Size of each subproblem =
The cost of dividing and combing =
logba =
The -class T(n) belongs =
Explanation / Answer
The Master method Provides a cookbook method for solving recurrence of the form T(n)=aT(n/b)+f(n) where a>=1 and b>1are constents and f(n) is an asymplotically possitive function .the master method requires memorization of three cases: 1.if((n^logba)f(n) then ?((n^logba)) 3.if((n^logba)=f(n) then ?(logn(n^logba))or ?(lognf(n)) 1)n is the size of the problem. 2)a is the number of subproblems in the recursion. 3)n/b is the size of each subproblem 4)f (n) is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions to the subproblems Solution: 1)- 1: a:1,b=10 2: no of Subproblem=1 3: Sige of each Subproblem:n/10 4: cost of deviding and combining:10^5 5: logba=0 6: The class T(n) belongs = ?(logn) 2)- 1: a:3,b=9 2: no of Subproblem=3 3: Sige of each Subproblem:n/9 4: cost of deviding and combining:n/100 5: logba=1/2 6: The class T(n) belongs = ?(n) 3)- 1: a:8,b=8 2: no of Subproblem=8 3: Sige of each Subproblem:n/8 4: cost of deviding and combining:8n 5: logba=1 6: The class T(n) belongs = ?(nlogn) 4)- 1: a:8,b=2 2: no of Subproblem=8 3: Sige of each Subproblem:n/2 4: cost of deviding and combining:3n 5: logba=3 6: The class T(n) belongs = if (f(n)=3n) then ?(n^3) where n>1 else if(f(n)=n^3)then ?(logn(n^3))Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.