Q15

MSQ1 mark

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $\Theta(n)$ ?

(A)

$T(n)=T(n-1)+1, \quad T(1)=1$

(B)

$T(n)=2 T\left(\frac{n}{2}\right)+1, \quad T(1)=1$

(C)

$T(n)=2 T\left(\frac{n}{2}\right)+n, \quad T(1)=1$

(D)

$T(n)=T(n-1)+n, \quad T(1)=1$

Loading…