Question 9893 – Time-Complexity
November 14, 2023Question 5475 – NIELIT Junior Teachnical Assistant_2016_march
November 15, 2023Question 9926 – Time-Complexity
If T1 = O(1), give the correct matching for the following pairs:
(M) Tn = Tn−1 + n (U) Tn = O(n) (N) Tn = Tn/2 + n (V) Tn = O(nlogn) (O) Tn = Tn/2 + nlogn (W) T = O(n2) (P) Tn = Tn−1 + logn (X) Tn = O(log2n)
Correct Answer: D
Question 8 Explanation:
(M) T(n) = Sum of first n natural nos. = n(n+1)/2 = O(n2)
(N) Apply Master’s theorem
T(n) = θ(n) = O(n)
(O) Apply Master’s theorem
T(n) = θ(n logn) = O(n logn)
(P) Here we are adding the log of firstn natural numbers.
So,
Tn = log1 + log2 + log3 + … + logn
= log (1×2×…n)
= log(n!)
= θ(n logn)
M – W N – V O – U P – X
M – W N – U O – X P – V
M – V N – W O – X P – U
None of the above
Subscribe
Login
0 Comments