Tambahan dari Pembahasan Kompleksitas Waktu Terbaik, Terburuk, dan Rata-rata

1. Diberikan sebuah matriks dengan ordo m x n (A₁ .. A_m, A₁ .. A_n), dengan tiap nilai pada elemen bernilai unik. Hitunglah kompleksitas waktu Terbaik( T min (n)), Terburuk(T max (n)), dan Rata-rata(T avg (n)) dari algoritma mencari elemen minimum larik di bawah ini.

Penyelesaian:

a.       Kasus terbaik (best case)

Adalah bila elemen ditemukan pada baris dan kolom (A_ij) pertama dan operasi (cari = A_ij) yang dilakukan sekali, sehingga: T­_min(n) = 1.

b.       Kasus terburuk (worst case)

Apabila jika elemen ditemukan pada baris dan kolom (A_ij) terakhir (l x m), sehingga: T_max(n) = n. (l x m = n)

c.       Kasus rerata (average case)

Apabila elemen atau operasi terhenti di antara kasus terbaik dan kasus terburuk, sehingga: 

2. Diberikan sebuah matriks dengan ordo m x n (A₁ .. A_m, A₁ .. A_n), dengan tiap nilai pada elemen bernilai unik. Hitunglah kompleksitas waktu Terbaik( T min (n)), Terburuk(T max (n)), dan Rata-rata(T avg (n)) dari algoritma mencari elemen minimum larik di bawah ini.

Penyelesaian:

a.       Kasus terbaik (best case)

Operasi akan terhenti sampai perulangan i dan j selesai, sehingga: T­_min(n) = n.

b.       Kasus terburuk (worst case)

Karena perulangan yang dilakukan menggunakan for, sehingga kasus terburuk sama dengan kasus terbaik: T_max(n) = n.

c.       Kasus rerata