Big O — Asymptotic Analysis

Hi, kembali lagi bersama saya rony, seorang software engineer yang mempunyai salah satu mimpi untuk dapat menulis buku komersil mengenai software engineering suatu saat nanti. Saat ini saya sendiri paling hanya sebatas international conference paper saja yang berisi hanya puluhan halaman, belum sampai di level sebuah buku komersil yang bisa sampai ratusan halaman. Bagi teman-teman semua yang sekiranya dapat berkolaborasi dengan saya untuk menggapai salah satu mimpi saya tersebut, tolong japri langsung ke saya. Saya tunggu ya .

Dan mari kita mulai pembahasan kali ini, yaitu mengenai Big O. Wow, mungkin ini adalah salah satu materi yang paling membuat saya bersemangat dalam menulis dibandingkan dari puluhan tulisan saya selama ini.

Semakin lama saya bergulat di dunia software engineering, terlebih lagi ketika sudah berjibaku di dunai software architecting, ada suatu hal yang saya sadari yaitu mengenai suatu pertanyaan mengenai apa yang sebenarnya menjadi tolok ukur sebuah code yang baik itu? Dan sekarang ini saya mungkin mempunyai suatu kesimpulan bahwa sebenarnya ada 2 tolok ukur yaitu Readability (Easy to Maintain) dan Scalability. Ya, tentu menjadi solutions architect itu memang menuntut saya berpikir lebih banyak ke arah yang sangat fundamental terhadap sesuatu. Contohnya adalah ketika menjawab pertanyaan seperti ini. Namun, pada pembahasan kali ini saya hanya akan membahas mengenai Scalability yang tentu nantinya akan berhubungan erat dengan Big O itu sendiri.

Saya akan memulai dengan menampilkan sebuah chart yang sangat penting di dunia Big O.

Kemudian saya akan memberikan memberikan beberapa percobaan sebagai berikut.

Jadi, berdasarkan Chart dan Percobaan yang telah dilakukan dapat kita ambil kesimpulan sebagai berikut.

• Kesimpulan 1 : Penambahan jumlah data (elements) itu akan berbanding lurus dengan penambahan waktu yang dibutuhkan untuk menjalankan task (numbers of operations needed) tersebut.
• Kesimpulan 2 : Di dalam Big O sendiri yang menjadi pokok bahasan adalah bagaimana kita membuat algoritma kita sebisa mungkin berada di area Excellent, Good, atau Fair. Dan kita perlu menghindari area Horrible dan Bad. Jadi, ini bukan merupakan sebuah kontradiksi dengan Kesimpulan 1.
• Kesimpulan 3 : Sebuah algoritma dikatakan Scalable salah satunya adalah apabila algoritma tersebut berada pada O(log n), O(1), atau O(n). Jadi, selain itu kita perlu lakukan refactoring agar dapat masuk ke dalam salah satu area notasi Big O tersebut.
• Kesimpulan 4 : Pada percobaan 1, 2, dan 3, function tersebut termasuk ke dalam O(n).

Kesimpulan 4 menyatakan bahwa Big O dari function tersebut adalah O(n). So, kenapa bisa O(n)?

Karena pada percobaan / function tersebut akan menghasilkan suatu grafik antara jumlah input data (elements) dan jumlah proses (numbers of operation) seperti berikut ini.

Ya, kita dapat dengan jelas melihat bahwa semakin banyak jumlah data maka jumlah proses yang diperlukan juga semakin bertambah secara Linear (time). Oleh karena itu, O(n) juga sering disebut Linear Time Big O. Dan O(n) ini adalah Big O yang paling sering kita jumpai di kehidupan seorang software engineer, ini juga yang mendasari mengapa saya membahas Big O ini pertama kali pada materi ini.

Kemudian, salah satu yang perlu kita harus ketahui adalah kapan kita dapat mengenali implementasi O(n) di software engineering? Apakah teman-teman sudah dapat menemukenalinya? Yup, O(n) dapat kita temui pada For Loops, While Loops, atau Loops secara umum yang melibatkan n items di dalamnya.

Sekarang mari kita bahas ke Big O lainnya yang juga cukup sering kita temui juga, silahkan perhatikan beberapa percobaan di bawah ini.

Satu hal penting yang paling terlihat pada percobaan tersebut adalah dimana dapat kita ketahui bahwa jumlah data yang kita gunakan tidak berpengaruh sama sekali ke performance function tersebut sehingga dapat kita simpulkan bahwa Big O tersebut adalah O(1) atau biasa kita sebut juga dengan Constant Time Big O. Pada O(1), kita hanya mengenal jumlah operations yang selalu sama yang diindikasikan juga dengan waktu yang selalu konstan (tetap) meskipun jumlah data berubah-ubah baik itu semakin kecil atau semakin besar. Contoh implementasi untuk O(1) ini bisa dikatakan adalah semua statement / function/ atau method yang tidak ada Loops di dalamnya. Kemudian di dalam grafik kita dapat lihat seperti di bawah ini.

Sekarang mari kita coba untuk melakukan sebuah perhitungan terhadap Big O yang sudah kita pelajari (O(1) dan O(n)). Pada Gambar 10 kita dapat melihat bahwa perhitungan Big O dapat kita lakukan dengan cara melakukan perhitungan line per line dari sebuah function atau scope tertentu hingga akhirnya kita mendapatkan total dari Big O secara keseluruhan terhadap function tersebut. Dengan hasil perhitungan tersebut kemudian kita dapat melihat apakah function kita termasuk scalable dan efisien atau justru sebaliknya. Yup, ini adalah langkah dasar yang biasanya saya minta untuk dilakukan teruntuk yang sedang mempelajari atau melakukan analisis terhadap scalability dan performance dari suatu code / function. Nantinya, di sepanjang perjalanan di materi ini akan saya perlihatkan bagaimana melakukan perhitungan Big O yang lebih baik, simple dan lebih cepat.

Mari kita lanjutkan bahasan kita untuk Big O lainnya, yaitu O (n ^ 2). Hemmm, apakah terlihat lebih menarik dari O (n) dan O(1)? Ya tentu saja karena memang Big O yang satu ini lebih butuh perhatian khusus karena Big O ini adalah salah satu yang harus kita hindari. Mari kita lihat percobaan di bawah ini.

Beberapa hal yang menarik di Percobaan 7 adalah sebagai berikut.

• Apabila kita menemui Nested Loop (ditandai dengan adanya Indentation) itu berarti menandakan multiplication (*) bukan Addition (+)
• Jumlah Menu yang dihasilkan adalah sebanyak 16 Menu, ini didapat dari multiplication (foods, drinks)

Dan apabila kita coba gambarkan ke dalam bentuk sebuah chart maka kita akan dapat melihat chart seperti berikut.

Jadi di dalam notasi Big O, sebuah program yang mengimplementasikan Nested Loop di dalamnya berarti program tersebut termasuk ke dalam O(n2). Kita ambil sebagai contoh di Gambar 12 tersebut, jika kita punya 2 elements maka akan membutuhkan 4 operations. Apabila kita menggunakan 3 elements, maka akan membutuhkan 9 operations. Dan apabila kita punya 4 elements seperti yang kita lakukan pada Percobaan 7 di Gambar 11, maka kita menghasilkan 16 operations.

Dan tentu kita sebagai software engineer yang baik harus menghindari hal tersebut dan mengubahnya ke dalam bentuk solusi yang lebih efisien sehingga bisa masuk ke O(n), O(log n), atau O(1). Bagaimana caranya? Ya, nanti saya akan berikan salah satu cara untuk melakukannya. Jadi, tolong bersabar ya. Kita perlu mempelajari banyak hal terlebih dahulu agar pemahaman kita lebih komprehensif.

Sekarang mari saya tunjukkan Big O terakhir yang akan saya masukkan dalam bahasan materi kali ini yaitu mengenai O(n!) atau Factorial Big O. Untuk Big O lainnya tidak akan saya bahas karena Big O lainnya sangat jarang ditemui di dalam pengembangan sebuah perangkat lunak terutama dari pengalaman pribadi saya sendiri selama ini.

O(n!) ini adalah Big O yang sangat harus / kudu banget / wajib sekali kita hindari (intinya mah harus direfactor ke dalam solusi lain) karena kita dapat melihat bahwa performance yang ditimbulkan dari implementasinya akan sangat buruk bahkan termasuk yang terburuk. Mari saya tunjukkan di dalam kasus percobaan di bawah ini.

Problem Statement : Ada beberapa kandidat calon presiden Indonesia di tahun 2024. Mereka akan dijadwalkan melakukan debat calon presiden dan mengambil nomor urut untuk identitas mereka nanti saat kampanye. Pada pertemuan tersebut tentu diperlukan beberapa kursi yang akan digunakan oleh calon-calon tersebut, kemudian bagaimana kita dapat mengatur kursi tersebut? Silahkan berikan alternatif dari pengaturan kursi untuk ketiga calon presiden tersebut!

Beberapa hal bisa kita ambil dari Percobaan 8 dan Percobaan 9 tersebut adalah sebagai berikut.

• Ketika kita menggunakan 3 data input maka menghasilkan 6 data output (3! = 6)
• Ketika kita menggunakan 4 data input maka menghasilkan 24 data output (4! = 24)
• Untuk jumlah pasti dari operations yang dibutuhkan tentu akan sangat bergantung dari algoritma yang digunakan, dalam contoh tersebut kita menggunakan approach recursive function.

Kemudian, bagaimana kita menemukenali Factorial Big O ini ? Yup, O(n!) punya ciri-ciri bahwa biasanya diindikasikan dengan adanya sebuah loop yang terdiri dari n items, dan kemudian ada penambahan loop lagi untuk n items tersebut. Silahkan perhatikan Gambar 13 dan Gambar 14 lagi, hal itu pun juga akan kita temui di dalam function tersebut.

Kita sudah mempelajari beberapa beberapa jenis dari Big O yang paling umum terjadi di dunia software engineering, dan untuk Big O yang lainnya tidak akan saya bahas karena sangat jarang kita temui di dalam praktiknya sehari-hari terutama sepengalaman saya sendiri yang sudah lebih dari 12 tahun berkutat di software engineering.

Sekarang, mari kita menuju pada The Rules of Big O. Di sini kita akan membahas beberapa prinsip atau aturan yang sangat penting di dalam Big O sehingga nantinya akan berpengaruh dalam proses analisis, kalkulasi, hingga akhirnya dapat membantu kita merancang solusi atas problem di Big O yang kita hadapi.

Big O Rule 1 : Worst Case Scenario is the most we care about / Drop non-dominant terms

Di Gambar 15 atau lebih tepatnya pada Percobaan 10, kita dapat melihat bahwa kita mempunyai sebuah function yang akan melihat apakah input merupakan salah satu perusahaan Telco atau bukan. Di function tersebut terdapat 10 perusahaan Telco besar, dan data itu lah yang dijadikan acuan apakah input (data perusahaan yang dimasukkan ) merupakan salah satu perusahaan Telco yang ada di dalam data tersebut. Kemudian kita juga harus sadar bahwa di dalam Hasil Percobaan 10, kita mendapati bahwa input tidak bisa kita pastikan karena memang tergantung dari kebutuhan atau data perusahaan yang ingin diverifikasi.

• Input ‘Telkom’ (0), maka hanya membutuhkan 1 kali proses searching
• Input ‘AT&T’ (4), maka hanya membutuhkan 5 kali proses searching
• Input ‘T-Mobile’ (10), maka membutuhkan 11 kali proses searching

Jadi, Big O Rule 1 ini menyatakan bahwa kita tidak bisa selalu berharap kondisi yang ideal seperti contohnya adalah input yang ideal, justru malah sebaliknya kita perlu memperhatikan kondisi yang paling tidak ideal sehingga menyebabkan program kita berjalan dalam keadaan paling tidak efisien. Oleh karena itu, pada Percobaan 10 tersebut kita dapat mengatakan secara bahwa function tersebut termasuk ke dalam O(n).

Big O Rule 2 : Remove Every Constants

Problem Statement : Tim marketing dan product mempunyai data customers yang berjumlah 100 buah mobile number. Mendekati akhir tahun, ada inisiatif untuk mengirimkan promo ke seluruh customer menggunakan data mobile number yang ada. Selain promo, ada juga discount khusus yang diberikan ke 10 orang saja dari customer yang terpilih oleh tim product.

Mari kita lihat Percobaan 11 dengan seksama, khususnya untuk function SendPromoDiscount. Dalam perhitungan Big O untuk function tersebut sebenarnya adalah terdiri dari O(n) dan O(10). Kemudian apabila kita coba untuk simplify maka menjadi O(n + 10). Kemudian, berdasarkan Big O Rule 2 yang menyatakan bahwa We Must Remove Every Constant, maka kemudian kita perlu mengabaikan O(10) tersebut karena untuk setiap Constant dianggap tidak terlalu berpengaruh di dalam perhitungan Big O karena sifatnya yang tetap. Itu berbeda apabila dibandingkan dengan O(n) yang punya sifat tidak tetap dan dapat memberikan dampak yang sangat besar terutama apabila n tersebut sangat besar.

Big O Rule 3 : Different Terms for Inputs

Untuk memahami Big O Rule 3 ini, silahkan perhatikan program pada Gambar 19 dan Gambar 20.

Big O Rule 3 menyatakan bahwa apabila kita mendapati sebuah function/program yang menggunakan data input yang berbeda, maka kita tidak bisa melakukan penyederhanaan/simplifikasi terhadap notasi Big O. Mengapa hal itu harus dilakukan? Karena data input yang berbeda dapat secara signifikan mempengaruhi complexity atau jumlah operasi yang dibutuhkan. Sebagai contohnya pada Percobaan 13 kita tahu bahwa data pertama(input1) membutuhkan 100.000.000 operasi sedangkan data kedua (input2) hanya membutuhkan 1000 operasi saja. Sedangkan apabila data input yang digunakan itu sama, maka kita dapat melakukan simplifikasi terhadap notasi Big O seperti terlihat pada Percobaan 12.

Berdasarkan Percobaan 12 dan Percobaan 13 kita dapat mengambil beberapa hal penting sebagai berikut.

• Berdasarkan Big O Rule 1, maka kita dapat mengabaikan O(2) yang ada.
• Berdasarkan Big O Rule 2, maka pada Percobaan 12 kita dapat mengabaikan Contants yang ada. Jadi, O(2n) dapat kita simplifikasi menjadi O(n) saja.
• Berdasarkan Big O Rule 3, maka pada Percobaan 13 tidak dapat kita lakukan simplifikasi sehingga notas Big O yang kita dapat adalah O(m + n)

Di dalam Big O sendiri biasanya juga mengenal Time Complexity(Speed) dan Space Complexity(Memory). Tapi, yang paling menjadi perhatian utama biasanya adalah seperti pada bahasan kita kali ini yaitu di dalam konteks Time Complexity (Speed). Untuk Space Complexity akan saya bahas di materi selanjutnya, namun semua materi kali ini tetap menjadi fundamental knowledge nantinya. Selain mengenai Space Complexity, saya juga akan membahas mengenai beberapa solusi atau teknik refactoring untuk mengatasi problems yang kita temui setelah melakukan analisis (Big O) di materi selanjutnya. Dan sudah barang tentu, itu akan semakin menarik, semakin challenging, dan semakin membuat kita menjadi software engineer yang lebih baik tentunya.

Sebagai penutup, saya akan memberikan beberapa hal yang biasanya dapat mempengaruhi Big O di dalam konteks Time Complexity.

• Function Calls : function(), outside function call
• Loops : for…loop, while…loop, foreach, etc
• Comparisons : <, >, ==, <=, >=, etc
• Operations : +, -, /, *, %, etc

Demikian bahasan kali ini, tentu materi saya pasti ada kekurangan sehingga saya memohon maaf atas hal tersebut. Dan apabila ada kritik atau saran silahkan langsung hubungi saya. Terakhir, semoga tulisan saya dapat bermanfaat. Terima kasih.

Original Article : https://www.linkedin.com/pulse/big-o-asymptotic-analysis-rony-setyawan