Consider the following recurrence and answer the questions given below T(n)= 3T(n/2) + 2n2 i.) a) How many sub problems
Posted: Mon Jun 06, 2022 1:20 pm
Consider the following recurrence and answer the questions
given
below
T(n)= 3T(n/2) + 2n2
i.) a) How many sub problems are in the above recurrence?
b) What the size of each of the sub problems identified
above?
c) What is the work/time needed for non-recursive part (divide
and
combine) of the recurrence?
ii) Use the recursive tree technique to obtain the running time
(time
complexity) of the above recurrence?
iii) Use the mater theorem to determine the time complexity of the
above
recurrence.
given
below
T(n)= 3T(n/2) + 2n2
i.) a) How many sub problems are in the above recurrence?
b) What the size of each of the sub problems identified
above?
c) What is the work/time needed for non-recursive part (divide
and
combine) of the recurrence?
ii) Use the recursive tree technique to obtain the running time
(time
complexity) of the above recurrence?
iii) Use the mater theorem to determine the time complexity of the
above
recurrence.