PrepSnap logoPrepSnap
Pass

Question

1.
2.
3.
4.
Answer (Detailed Solution Below)

Option 2 : Θ(n²)

Advertisement

Detailed Solution

सही उत्तर Θ(n²) है।

Key Points
Helpful?
PrepSnapprepsnap.in • Part -A

Question:

By the Master theorem, what is the asymptotic time complexity of the recurrence T(n) = 3T(n/2) + Θ(n²)? / मास्टर प्रमेय से, पुनरावृत्ति T(n) = 3T(n/2) + Θ(n²) की अनंतस्पर्शी समय जटिलता क्या है?

1.
Θ(n log n)
2.
Θ(n²)
3.
Θ(n^1.585)
4.
Θ(n² log n)

Correct Answer: Θ(n²)

Here a = 3, b = 2 and f(n) = Θ(n²); since n^(log₂3) ≈ n^1.585 is polynomially smaller than n², Master case 3 gives T(n) = Θ(n²). / यहाँ a = 3, b = 2 और f(n) = Θ(n²); चूँकि n^(log₂3) ≈ n^1.585 बहुपदीय रूप से n² से छोटा है, मास्टर केस 3 से T(n) = Θ(n²)।

Downloaded from PrepSnap (prepsnap.in)