Soal SMA · Analisis · Kesulitan 3/5
Sebuah algoritma memiliki kompleksitas waktu T(n) = 3T(n/2) + n². Dengan menggunakan Master Theorem, berapa kompleksitas waktu asimtotiknya?
- A.O(n²)
- B.O(n² log n)
- C.O(n³)
- D.O(nlog_² ³)
Kunci jawaban & pembahasan
Jawaban: O(n²)
Master Theorem: a=3, b=2, f(n)=n². Bandingkan nlog_b a = nlog_² ³ ≈ n¹.⁵⁸⁵ dengan f(n)=n². Karena f(n) = Ω(nlog_b a ⁺ ε) dengan ε≈0.415, maka T(n)=Θ(f(n))=O(n²).
Mau penjelasan yang menyesuaikan level anak?
Xinau AI membahas soal langkah demi langkah, menyesuaikan gaya bahasa dengan usia anak, dan menyusun latihan berikutnya berdasarkan jawaban sebelumnya.
Coba gratis 30 hari