Soal SMA · Soal cerita · Kesulitan 3/5
Seorang siswa mengukur waktu eksekusi sebuah algoritma pada input berukuran n. Ia mencatat bahwa waktu eksekusi T(n) memenuhi hubungan T(2n) = 3·T(n) + 5n, dengan T(1) = 2. Jika n adalah pangkat dua, maka kompleksitas asimtotik T(n) yang paling tepat adalah...
- A.O(n log n)
- B.O(n¹.585)
- C.O(n²)
- D.O(n log² n)
Kunci jawaban & pembahasan
Jawaban: O(n¹.585)
Relasi rekurens T(2n)=3T(n)+5n setara dengan T(n)=3T(n/2)+5n; dengan Master Theorem a=3, b=2, log_b a ≈ 1,585 > 1 sehingga T(n)=Θ(n¹.585).
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