Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas konsep Big-O dan Big-Omega dalam Matematika Diskrit. Big Omega digunakan untuk membandingkan dua fungsi, Fx dan Gx, dengan konstanta C dan K sebagai saksi perbandingan nilai mutlaknya. Sedangkan Big O, juga membandingkan dua fungsi, namun Gx menjadi batas atasnya. Konsep ini penting dalam mengukur kompleksitas algoritma dan menentukan pertambahan operasi saat nilai X membesar.

Di dalam perhitungan algoritma itu, seringkali kecepatan itu tidak dihitung berapa cepat suatu algoritma itu selesai.

Atau untuk menghitung suatu fungsi tertentu itu selesai.

Karena kalau waktunya itu berdasarkan detik, itu bergantung pada komputer yang kita pakai.

Yang canggih komputernya pasti semakin cepat.

Kalau ini kita akan menghitung berapa banyak pertambahan atau laju kecepatannya

untuk menghitung banyaknya operasi di situ kalau X-nya membesar.

Atau apakah dia sama dengan kalau menghitung fungsi polinomial,

atau dia sama kalau menghitung fungsi eksponensial, seperti itu.

Ada dua ukuran yang kita pakai, yaitu Big Omega dan Big O.

Big Omega sendiri, kalau kita punya dua fungsi FG yang memetakan himpunan bilangan bulat

atau kehimpunan bilangan real, maka si Fx itu disebut sebagai Omega Gx.

sedemikian sehingga harga mutlak Fx-nya itu lebih besar sama dengan C dikali harga mutlak Gx,

Jadi di sini selain dua fungsi yang kita bandingkan, Fx dengan Gx,

kita juga punya konstanta C dan K yang kita sebut sebagai saksi

bahwa komparasi antara nilai mutlak Fx dengan nilai mutlak Gx itu seperti apa.

Kalau di sini, karena nilai harga mutlak Fx itu dicari C-nya dan K-nya,

sedemikian sehingga harga mutlak Fx tadi lebih besar sama dengan C dikali harga mutlak Gx,

Maka si Gx itu seperti menjadi batas bawah dari fungsinya.

Kalau O, sama sih sebetulnya kita punya dua fungsi yang memetakan

himpunan bilangan bulat atau kehimpunan bilangan real,

kemudian kita akan mengatakan bahwa Fx adalah O dari fungsi Gx

sehingga harga mutlak Fx itu lebih kecil sama dengan C dikali harga mutlak Gx

Jadi di sini kita punya dua konstanta C dan K yang menjadi saksi perbandingan

antara harga mutlak Fx dengan harga mutlak Gx.

Bedanya dengan O tadi adalah kalau O itu Gx menjadi batas bawah.

Jadi kalau kita bisa menemukan C dan K yang itu,

Untuk selanjutnya kita hanya bahas O saja.

Jadi yang O itu tidak dibahas secara detail,

tapi biasanya keduanya itu merupakan suatu ukuran yang baik

sedangkan kalau O itu Gx akan menjadi batas bawahnya.