Site navigation

Match the following : List-I List-II A. T(n) = T(n - 1) + n 1. Θ(n2) B. T(n) = T(n/2) + c 2. Θ(logn) C.…

- A. \(T(n) = T(n-1) + n = \sum_{i=1}^n i = \Theta(n^2)\) (1) - B. \(T(n) = T(n/2) + c = \Theta(\log n)\) by Master Theorem Case 2 (2) - C. \(T(n) = T(n/2) + n = \Theta(n)\)…

Choose your answer

Match the following :

List-I List-II
A. T(n) = T(n - 1) + n 1. Θ(n2)
B. T(n) = T(n/2) + c 2. Θ(logn)
C. T(n) = T(n/2) + n 3. Θ(n)
D. T(n) = 2T(n/2) + 1 4. Θ(nlogn)

Codes :
A B C D

Select one answer
Answer and explanation

Correct answer B

- A. T(n)=T(n−1)+n=∑i=1ni=Θ(n2)T(n) = T(n-1) + n = \sum_{i=1}^n i = \Theta(n^2) (1)
- B. T(n)=T(n/2)+c=Θ(log⁡n)T(n) = T(n/2) + c = \Theta(\log n) by Master Theorem Case 2 (2)
- C. T(n)=T(n/2)+n=Θ(n)T(n) = T(n/2) + n = \Theta(n) by Master Theorem Case 3 (3)
- D. T(n)=2T(n/2)+1=Θ(nlog⁡22)=Θ(n)T(n) = 2T(n/2) + 1 = \Theta(n^{\log_2 2}) = \Theta(n) by Master Theorem Case 1 (3).

Practice for these exams

  • Rajasthan Vice Principal Iti Computer Science

Related question papers

Related questions in this topic