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 2:35 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.
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.