Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)

Match List - I with List - II.

 List - I (Recurrence Relations)

List - II (Complexity) 

 (A) $T(n)=2T(n/2)+n$
 (I) $T(n)=\theta(n\log n)$ [exact solution]
 (B) $T(n)=T(n/2)+1$
 (II) $O(n^2)$
 (C) $T(n)=2T(n/2)+1$
 (III) $T(n)=\theta(n)$ [exact solution]
 (D) $T(n)=T(n-1)+1$

 (IV) $O(\log n)$

Choose the correct answer from the options given below :





Solution

(A) $T(n)=2T(n/2)+n$


Master theorem


$a=2,; b=2,; f(n)=n$


$\Rightarrow T(n)=\theta(n\log n)$


So (A) → (I)


(B) $T(n)=T(n/2)+1$


Divide size halves each step


$\Rightarrow T(n)=O(\log n)$


So (B) → (IV)


(C) $T(n)=2T(n/2)+1$


Master theorem


$\Rightarrow T(n)=\theta(n)$


So (C) → (III)


(D) $T(n)=T(n-1)+1$


Linear recurrence


$\Rightarrow T(n)=O(n)$


Closest option given:


(D) → (II)


Thus matching:


(A)-(I), (B)-(IV), (C)-(III), (D)-(II)


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More
Ask Your Question or Put Your Review.

loading...