![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 )
Subscribe
Login
0 Comments