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

Video ini membahas contoh estimasi ukuran fungsi dalam Matematika Diskrit dengan teknik perhitungan lanjutan. Contoh-contoh mencakup pencarian biner dan penentuan elemen maksimum serta minimum dalam sebuah barisan. Dengan menerapkan teorema yang sesuai, estimasi big O dari fungsi-fungsi tersebut dapat ditentukan secara efisien, seperti big O dari log n untuk pencarian biner dan O n untuk penentuan elemen maksimum dan minimum.

Sekarang kita lihat contoh untuk mencari estimasi big O dari contoh-contoh pada saat kita membahas divide and conquer.

Misalnya untuk pencarian binar, untuk pencarian binar itu kita sudah mendapatkan nilai fn itu sama dengan f dari n per 2 ditambah 2.

Kalau n nya genap ya karena itu kan apa namanya mencari dibagi 2 gitu.

Jadi f itu adalah banyak perbandingan yang dibutuhkan untuk pencarian binar pada barisan berukuran n.

Karena bentuknya ini adalah bentuk yang sama dengan yang di teorema 1,

jadi di sini di teorema 1 kan tadi bentuknya adalah a x f dari n per b plus c.

Nah di sini b nya jadi sama dengan 2, ini n per 2 berarti b nya 2 dan 2 yang di belakang itu adalah c nya.

Nanti kita akan dapat karena di sini a nya itu sama dengan 1 berarti fn itu adalah big O dari log n.

Jadi kita enggak usah nyari apa namanya panjang lebar kita menggunakan langsung teorema 1.

Nah contoh yang lain juga untuk perbandingan yang digunakan untuk menentukan elemen maksimum dan minimum dari suatu barisan.

Itu juga sama karena fn nya itu sama dengan 2 kali f dari n per 2 plus 2 maka big O nya adalah O n.