10.19.2023
Question 1: Which of the following is the appropriate recurrence relation for the time complexity of a recursive function that generates Fibonacci numbers?
(3 points)
A. $T(n)=T(n-1)+c_{1};T(0)=0, \; T(1)=1$
B. $T(n)=T(n/2)+c_{1}; T(0)=0, \; T(1)=1$
C. $T(n)=T(n-1)+T(n-2); T(0)=0, \; T(1)=1$
D. $T(n)=T(n/2)+c_{1}n; T(0)=0, \; T(1)=1$
Answer
C. $T(n)=T(n-1)+T(n-2); T(0)=0, \; T(1)=1$Question 2: Which of the following is the appropriate recurrence relation for the time complexity of a recursive function that executes Binary Search?
(3 points)
A. $T(n)=T(n-1)+c_{1}; T(1)=1$
B. $T(n)=T(n/2)+c_{1}; T(1)=1$
C. $T(n)=T(n-1)+c_{1}n; T(1)=1$
D. $T(n)=T(n/2)+c_{1}n; T(1)=1$
Answer
B. $T(n)=T(n/2)+c_{1}; T(1)=1$Question 3: Which of the following is the appropriate recurrence relation for the time complexity of a recursive function that executes Merge Sort?
(3 points)
A. $T(n)=2 \times T(n/2)+c_{1}n;T(1)=1$
B. $T(n)=T(n/2)+c_{1}; T(1)=1$
C. $T(n)=T(n-1)+c_{1}; T(1)=1$
D. $T(n)=T(n-2)+c_{1}n; T(1)=1$