T(n) = 2 T(n/2) + n lg lg n T(n) = 4 T(n/2) +n (i) (ii) (iii) T(n) = 4 T(n/2) + n lg lg n (iv) T(n) = 4 T(n/2) + n² %3D (v) T(n) = 4 T(n/2) + n² lg lg n %3D (vi) T(n) = 4 T(n/2) + n³ (vii) T(n) = 4 T(n/2) + n³ lg lg n %3D Among the above recurrences, please indicates those that can be solved by
Please refer to the attachment for the question. I know there's quite a few options, may I request in particular option (i), (iii), (v) and (viii)?
The answer given to me is (i) = No, (iii) = Yes, case 1, (v) = No, (vii) = Yes, case 3 but I don't know how to differentiate whether master theorem is applicable despite having the same or similar f(n). Thank you.
The master method is a formula for solving recurrence relations of the form:
T(n) = aT(n/b) + f(n),
where,
n = size of input
a = number of subproblems in the recursion
n/b = size of each subproblem. All subproblems are assumed
to have the same size.
f(n) = cost of the work done outside the recursive call,
which includes the cost of dividing the problem and
cost of merging the solutions
Step by step
Solved in 3 steps with 1 images
