Lembar kerja Algoritma & kompleksitas dengan jawaban

Notasi manakah yang menyatakan batas atas (upper bound) pertumbuhan?

1. ABig Theta
2. BLittle omega
3. CBig Omega
4. DBig O

Berapa kompleksitas waktu kasus terbaik insertion sort, pada array yang sudah terurut?

1. AO(n log n)
2. BO(n²)
3. CO(1)
4. DO(n)

Apa yang dimaksud dengan rekursi?

1. ALoop yang tidak pernah berakhir
2. BSejenis struktur data
3. CFungsi yang memanggil dirinya sendiri dengan input yang lebih kecil
4. DSebuah metode pengurutan

Berapa kompleksitas waktu dari: for i = 1 to n: for j = 1 to i: lakukan kerja O(1)?

1. AO(n log n)
2. BO(n)
3. CO(n³)
4. DO(n²)

Algoritma greedy:

1. AMengambil pilihan terbaik secara lokal pada setiap langkah
2. BMencoba setiap solusi yang mungkin
3. CHanya menggunakan rekursi
4. DSelalu memberikan solusi optimal

Quicksort selalu memakai elemen pertama sebagai pivot. Pada input mana algoritma ini menunjukkan perilaku kasus terburuknya?

1. AArray yang semua elemennya berbeda
2. BArray dalam urutan acak
3. CArray yang sudah terurut
4. DArray dengan panjang 2

Insertion sort berjalan dalam O(n) pada input terurut. Apakah ini bertentangan dengan batas bawah Ω(n log n) untuk pengurutan berbasis perbandingan?

1. ATidak, batas bawah itu berlaku untuk kasus terburuk atas semua input, bukan untuk setiap input
2. BYa, sehingga batas bawah itu salah
3. CTidak, karena insertion sort bukan pengurutan berbasis perbandingan
4. DYa, tetapi hanya untuk array yang lebih pendek dari 100

Mengapa algoritma Dijkstra dapat memberikan hasil yang salah ketika sebagian bobot sisi negatif?

1. ASimpul ditetapkan final saat diekstraksi, tetapi sisi negatif berikutnya masih dapat memberinya lintasan yang lebih pendek
2. BAlgoritma itu masuk ke loop tak hingga pada setiap sisi negatif
3. CBilangan negatif tidak dapat disimpan dalam priority queue
4. DAlgoritma itu hanya bekerja pada graf tak berarah