Programmer yang baik harus mampu memprediksi jumlah sumber daya yang akan ‘dihabiskan’ oleh kode yang ditulisnya. Untuk dapat mengukur hal tersebut, seorang programmer harus mengetahui seberapa efisien algoritma yang telah dia tulis. Efisiensi algoritma dapat diukur dengan sebuah notasi yang bernama Big O. Big O adalah sebuah metrik yang digunakan untuk mengukur kompleksitas suatu algoritma. Kompleksitas dalam konteks ini berkaitan dengan efisiensi kode. Semakin rendah kompleksitasnya, semakin efisien pula kode tersebut.

Notasi Big O mengukur kompleksitas algoritma dalam dimensi waktu. Selain Big O, ada dua notasi lain yang dapat digunakan untuk mengukur kompleksitas waktu sebuah algoritma, yaitu Big Theta dan Big Omega. Konsep Big Omega mirip dengan Big O. Perbedaan kedua konsep tersebut terletak pada semantiknya. Nilai Big Omega menunjukkan batas bawah kompleksitas waktu suatu algoritma, sedangkan Big O sebaliknya. Apabila sebuah algoritma memiliki nilai batas atas dan batas bawah yang sama, algoritma tersebut dikatakan memenuhi konsep Big Theta.

Jika Anda seorang programmer, Anda tidak perlu memahami semua notasi yang ada. Notasi Big O, Big Omega, dan Big Theta lebih sering digunakan oleh para akademisi. Dalam praktiknya di industri teknologi, orang-orang menganggap Big O dan Big Theta sebagai satu konsep yang sama. Di samping itu, notasi Big Omega sangat jarang digunakan. Alasannya cukup sederhana. Sebagian besar orang cenderung lebih tertarik untuk mengetahui waktu eksekusi paling lama yang mungkin terjadi. Dengan kata lain, konsep Big O saja sudah cukup untuk keperluan analisis algoritma seorang programmer.

Sebagai sesuatu yang abstrak, konsep Big O dapat lebih mudah dipahami dengan menggunakan sebuah analogi. Bayangkan Anda memiliki sebuah hard drive berisi data penting yang perlu diberikan kepada teman Anda di luar kota secepatnya. Dalam kasus ini, ada dua alternatif yang dapat dilakukan. Anda bisa melakukan transfer data secara digital atau memberikan hard drive tersebut kepada teman Anda. Dengan alasan efisiensi waktu, tentu saja Anda akan memilih alternatif pertama karena mengirimkan hard drive dapat memakan waktu 3 hingga 5 jam. Namun, bagaimana jika data yang harus dikirimkan sangat besar, misalnya 1 TB? Dengan kecepatan rata-rata internet saat ini (16 Mbps), diperlukan waktu lebih dari satu hari untuk menyelesaikan pengiriman data. Dengan kondisi tersebut, alternatif kedua tentunya menjadi pilihan.

Dalam analogi di atas, proses transfer data mewakili waktu eksekusi (runtime) algoritma. Dalam notasi Big O, proses tersebut dapat dideskripsikan sebagai berikut.

Transfer digital: O(n), di mana n adalah ukuran data. Notasi tersebut menunjukkan bahwa waktu yang diperlukan untuk transfer data akan bertambah secara linear mengikuti besar ukuran data. Transfer fisik: O(1), di mana 1 adalah suatu konstanta. Nilai konstan dalam notasi tersebut menunjukkan bahwa ukuran data tidak memengaruhi waktu transfer data. Artinya, data akan selalu sampai dalam rentang waktu 3 – 5 jam, tidak peduli seberapa besar data yang dikirimkan Selain O(n) dan O(1), masih banyak variasi runtime lainnya. Beberapa jenis runtime yang umum ditemui adalah O(log n), O(n log n), O(n^2), O(2^n), dan O(n!). Grafik di bawah ini menunjukkan perbandingan setiap runtime tersebut.

Sebuah runtime mungkin saja memiliki lebih dari satu variabel. Sebagai contoh, Anda ingin mengecat dinding kamar. Apabila dinding tersebut memiliki lebar l dan memerlukan n lapis cat, waktu total yang diperlukan dapat dirumuskan sebagai O(ln). Penjelasan lebih detil terkait penentuan nilai kompleksitas dari sebuah algoritma akan dijelaskan dalam artikel berikutnya.

Kompleksitas algoritma adalah hal mendasar yang seharusnya dipahami oleh programmer. Pemahaman yang kurang terhadap hal tersebut dapat menimbulkan kerugian. Sebagai seorang programmer, Anda tidak bisa menilai dalam kasus apa algoritma Anda berjalan lebih cepat atau lebih lambat. Selain itu, ketidakmampuan tersebut mungkin saja akan berujung pada kritik dan penilaian buruk terhadap kinerja Anda. Oleh karena itu, menguasai konsep Big O adalah suatu kewajiban jika Anda ingin menjadi programmer yang unggul.