Question:
What is the tight asymptotic time complexity of the recurrence relation \(T(n) = 3T(n/2) + n \log n\)?
पुनरावृत्ति संबंध \(T(n) = 3T(n/2) + n \log n\) की सटीक स्पर्शोन्मुख समय जटिलता (time complexity) क्या है?
Options:
- \(\Theta(n^{\log_2 3})\)
- \(\Theta(n \log n)\)
- \(\Theta(n^2)\)
- \(\Theta(n^{\log_2 3} \log n)\)
- \(\Theta(n^{\log_2 3})\)
- \(\Theta(n \log n)\)
- \(\Theta(n^2)\)
- \(\Theta(n^{\log_2 3} \log n)\)
Correct Answer: a)
Explanation:
Using Master Theorem for \(T(n) = aT(n/b) + f(n)\):
Here \(a = 3\), \(b = 2\), so \(n^{\log_b a} = n^{\log_2 3} \approx n^{1.585}\).
Now compare with \(f(n) = n \log n\).
Since \(1.585 > 1\), there exists \(\epsilon > 0\) (e.g. \(\epsilon \approx 0.585 – 0.1\)) such that \(f(n) = O(n^{\log_2 3 – \epsilon})\).
This falls strictly into Case 1 of Master Theorem.
Therefore, \(T(n) = \Theta(n^{\log_2 3})\).
Here \(a = 3\), \(b = 2\), so \(n^{\log_b a} = n^{\log_2 3} \approx n^{1.585}\).
Now compare with \(f(n) = n \log n\).
Since \(1.585 > 1\), there exists \(\epsilon > 0\) (e.g. \(\epsilon \approx 0.585 – 0.1\)) such that \(f(n) = O(n^{\log_2 3 – \epsilon})\).
This falls strictly into Case 1 of Master Theorem.
Therefore, \(T(n) = \Theta(n^{\log_2 3})\).
मास्टर प्रमेय के अनुसार: \(a = 3, b = 2\)
\(n^{\log_b a} = n^{\log_2 3} \approx n^{1.585}\)
चूंकि \(f(n) = n \log n\) का मान \(n^{\log_2 3}\) से बहुपद रूप में छोटा है (Case 1 लागू होता है)।
अतः \(T(n) = \Theta(n^{\log_2 3})\)।
\(n^{\log_b a} = n^{\log_2 3} \approx n^{1.585}\)
चूंकि \(f(n) = n \log n\) का मान \(n^{\log_2 3}\) से बहुपद रूप में छोटा है (Case 1 लागू होता है)।
अतः \(T(n) = \Theta(n^{\log_2 3})\)।