![Nielit Scentist-B [02-12-2018]](https://solutionsadda.in/wp-content/uploads/2019/05/green-new-logo.png){kind=logo}
NIC-NIELIT Scientist-B 2020
October 3, 2023NIC-NIELIT Scientist-B 2020
October 3, 2023Nielit Scentist-B [02-12-2018]
|
Question 1
|
For the given recurrence equation
T(n)=2T(n-1), if n>0.
=1, otherwise
T(n)=2T(n-1), if n>0.
=1, otherwise
|
O(nlogn)
|
|
|
O(n2)
|
|
|
O(2n)
|
|
|
O(n)
|
Question 1 Explanation:
T(n) = 2T (n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 22 T(n – 2) + 3
⋮
= 2kT(n – k) + (2k – 1)
= 2n-1T(1) + (2n-1 – 1)
= 2n-1+ 2n-1 – 1
= 2n – 1
≅ O( 2n )
= 2 [2T(n – 2) + 1] + 1
= 22 T(n – 2) + 3
⋮
= 2kT(n – k) + (2k – 1)
= 2n-1T(1) + (2n-1 – 1)
= 2n-1+ 2n-1 – 1
= 2n – 1
≅ O( 2n )
Correct Answer: C
Question 1 Explanation:
T(n) = 2T (n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 22 T(n – 2) + 3
⋮
= 2kT(n – k) + (2k – 1)
= 2n-1T(1) + (2n-1 – 1)
= 2n-1+ 2n-1 – 1
= 2n – 1
≅ O( 2n )
= 2 [2T(n – 2) + 1] + 1
= 22 T(n – 2) + 3
⋮
= 2kT(n – k) + (2k – 1)
= 2n-1T(1) + (2n-1 – 1)
= 2n-1+ 2n-1 – 1
= 2n – 1
≅ O( 2n )