Kompleksitas Algoritma

Algoritma adalah urutan langkah-langkah logis penyelesaian masalah yang disusun secara sistematis dan logis. Sebuah algoritma tidak saja harus benar, tetapi juga harus efisien. Algoritma yang bagus adalah algoritma yang efektif dan efisien. Untuk dapat mengetahui seberapa efisien suatu algoritma, dipakailah teori kompleksitas algoritma sebagai dasar kajian. Kompleksitas terbagi atas dua, yaitu kompleksitas waktu dan kompleksitas ruang.

Kompleksitas Waktu, T(n), adalah jumlah operasi yang dilakukan untuk melaksanakan algoritma sebagai fungsi dari ukuran masukan n. Maka, dalam mengukur kompleksitas waktu dihitunglah banyaknya operasi yang dilakukan oleh algoritma. Idealnya, kita memang harus menghitung semua operasi yang ada dalam suatu algoritma. Namun, untuk lasan praktis, cukup menghitung jumlah operasi abstrak yang mendasari suatu algoritma. Operasi abstrak ini disebut Operasi Dasar. 

Pada algoritma pengurutan, terutama pada pengurutan dengan perbandingan, operasi dasar adalah operasioperasi perbandingan elemen-elemen suatu larik dan operasi pertukaran elemen. Kedua hal itu dihitung secara terpisah, karena jumlah keduanya tidaklah sama. Biasanya kompleksitas algoritma dinyatakan secara asimptotik dengan notasi big-O. Jika kompleksitas waktu untuk menjalankan suatu algoritma dinyatakan dengan T(n), dan memenuhi T(n) ≤ C(f(n)) untuk n ≥ n0, maka kompleksitas dapat dinyatakan dengan:

Terdapat 2 jenis penggunaan notasi Big O, yaitu :

1. Infinite asymptotics
2. Infinitesimal asymptotics

Perbedaan kedua jenis penggunaan notasi ini hanya pada aplikasi. Sebagai contoh, pada infinite asymptotics dengan persamaan

Untuk n yang besar, pertumbuhan T(n) akan sebanding dengan n2 dan dengan mengabaikan suku yang tidak mendominasi kita, maka kita tuliskan:

 

Pada infinitesimal asymptotics, Big O digunakan untuk menjelaskan kesalahan dalam aproksimasi untuk sebuah fungsi matematika, sebagai contoh:

Kesalahannya memiliki selisih: