Question
1.
2.
3.
4.
Answer (Detailed Solution Below)
Option 4 : $O(n \log n)$
Advertisement
Detailed Solution
सही उत्तर $O(n \log n)$ है।
Key Points
Helpful?
prepsnap.in • Part -AQuestion:
What is the asymptotic solution of the recurrence $T(n) = 2T(n/2) + n$ with $T(1) = 1$? / पुनरावृत्ति $T(n) = 2T(n/2) + n$, $T(1) = 1$ का अनंतस्पर्शी हल क्या है?
1.
$O(n)$
2.
$O(n^2)$
3.
$O(\log n)$
4.
$O(n \log n)$
Correct Answer: $O(n \log n)$
By the Master Theorem, $a = 2$, $b = 2$, $f(n) = n = \Theta(n^{\log_2 2})$, which is Case 2, giving $T(n) = \Theta(n \log n)$. / मास्टर प्रमेय से, $a = 2$, $b = 2$, $f(n) = n = \Theta(n^{\log_2 2})$, यह स्थिति 2 है, अतः $T(n) = \Theta(n \log n)$।
Downloaded from PrepSnap (prepsnap.in)