Dodi adalah anak yang nakal. Sebagai hukuman atas kenakalan tersebut, guru Dodi pun memberi PR pada Dodi. Ia harus menentukan untuk 100 bilangan, apakah bilangan tersebut prima atau bukan. Dodi pun mengecek apakah bilangan tersebut dapat habis dibagi oleh 2 sampai float dari akar kuadrat bilangan tersebut (float= pembulatan ke atas) dengan sebuah program komputer.
Kompleksitas waktu algoritma Dodi di atas adalah ...
A. O(n)
B. O(n/2)
C. O(√n)
D. O(n²)
E. O(n√n)
Kompleksitas waktu algoritma Dodi di atas adalah ...
A. O(n)
B. O(n/2)
C. O(√n)
D. O(n²)
E. O(n√n)
Jawaban:
C. O(√n)
kompleksitas waktu adalah perkiraan lama waktu bagi sebuah algoritma. Jadi kompleksitas waktu algoritma nya adalah O(√n) Karena pada soal tertulis dibagi 2 sampai akar kuadrat bilangan tersebut, maka pada kasus paling buruk(yaitu sampai akar kuadrat bilangan) dan itu adalah √n
Semoga bermanfaat