Dalam modul sebelumnya telah dibahas Asymptotic Analysis yaitu menganalisis suatu performa dari algoritma dan struktur data dengan menggunakan pertumbuhan f(n) berdasarkan besar n yang berbeda-beda. Namun, metode seperti itu tidak efisien karena perlu menginputkan berbagai nilai dari n untuk memastikan hasil yang tepat dan kita tidak mengetahui pada nilai n berapa kondisi perbandingan akan berubah atau bahkan tidak. Berakar dari permasalahan tersebut maka terdapat suatu notasi yang disebut dengan Big O Notation atau O(n).

Big O notation adalah sebuah notasi yang dapat membantu kita dalam mencari pertumbuhan hasil dari fungsi tanpa harus melakukan input secara berulang terhadap banyak nilai n. Dalam penggunaannya, Big O Notation nantinya akan memberikan hasil berupa batas atas dari hasil fungsi sehingga hasil fungsi tidak akan lebih dari hasil dari Big O Notation atau f(n) <= O(n). Oleh karena itu, Big O notation dapat dikatakan adalah kondisi terburuk dari suatu algoritma dan struktur data.

Selain itu Big O Notation juga membuang ekpresi atau konstanta yang tidak diperlukan dalam sebuah fungsi. Perhatikan contoh berikut:

Dengan menggunakan Big O Notation kita dapat membuang konstanta atau ekspresi yang tidak diperlukan pada $f(n)$ yaitu 4 tanpa harus menginputkan satu persatu nilai n. Pemilihan konstanta bernilai 6 memiliki tujuan mencari nilai dai c.g(n) yang akan menghasilkan nilai yang lebih besar dari n sehingga kondisi g(n) >= f(n) dapat terpenuhi dengan ditemukan juga nilai n naught.

Pada bagian ini kita akan mencoba mencari tau kompleksitas dari looping berdasarkan kondisi yang diberikan pada looping.

for(int a = 0; a <= n; a++){
   printf("%d ", a);
}

Pada looping di atas, looping akan terjadi hingga nilai a sama dengan n, sehingga perulangan yang terjadi adalah sebanyak n kali. Untuk itu, dalam kode program di atas maka big O notationnya adalah O(n) atau linear time. Mari kita beralih ke Nested Loop.

for(int a = 0; a <= n; a++){
   for(int b = 0; b <= n; b++){
     printf("%d %d\n", a, b);
   }
}

Seperti kita ketahui setiap perulangan a akan melakukan n kali perulangan b, hal tersebut berulang ulang terjadi hingga a memiliki nilai sama dengan n. Perhatikan tabel berikut:

Dengan demikian looping a melakukan perulangan sebanyak n kali sedangkan looping b melakukan perulangan sebanyak n kali per perulangan a sehingga output akan dilakukan sebanyakan n x n atau $n^2$ kali. Untuk itu Big O Notation untuk program di atas adalah O($n^2$).

Selain looping, juga teradpat IF - Else complexity yang perlu diketahui cara menganilisnya. Dalam IF - Else kompleksitas dihitung dengan menjumlahkan running time test condition dengan running time terbesar milik statment di dalam IF-Else tersebut. Perhatikan contoh berikut:

    int a = 10 //--> 1
    if(a = 0){ // --> 1
        printf("hello apakabar"); // --> 1
    }else{ // --> 1
        for(int x = 0; x < n; x++){
            printf("hello apakabar 2"); // --> O(n)
        }
    }

Dalam program di atas terdapat 4 statement yang memiliki waktu konstan yaitu deklarasi variabel, 2 kali pengecekan kondisi, dan statement pada kondisi IF. Jika ditotalkan maka akan menghasilkan 1 + 1 + 1 + 1 = 4 yang mana hasil tersebut adalah sama dengan O(1) atau konstan complexity yang berarti sebuah kompleksitas yang tidak dipengaruhi oleh jumlah inputan yang diberikan dan bernilai 1. Kemudian, terdapat statement pada else berupa looping yang akan melakukan perulangan statement sejumlah n kali yang berarti running time pada bagian tersebut memiliki running time O(n) atau linear complexity yang bernilai n. Dengan demikian time complexity dari program di atas adalah f(n) = n + 1. Kemudian jika kita cari Big O Notationnya dengan cara yang telah dijelaskan di atas, maka akan menghasilkan O(n) atau linear complexity.

Logarithmic atau logaritma adalah invers dari perpangkatan. Logaritma menghitung berapa pangkat yang diperlukan untuk sebuah angka menghasilkan suatu nilai. Dalam kata lain dalam logaritma n adalah pangkat seperti berikut log₂(n)

Kompleksitas logaritma akan dicapai ketika besar dari masalah menjadi lebih kecil. Contoh dari kompleksitas logaritma adalah sebagai berikut:

for(int a = 1; a <= n;){
   a = a*2;
}

Pada program di atas, nilai a akan selalu dikalikan oleh 2 disetiap perulangannya sehingga menghasilkan nilai berikut:

Dengan begitu maka di akhir program nilai iterasi = n = 2^k-1 dan sehingga k = log₂(n) + 1 yang mana senilai dengan O(log₂n). Contoh:

for(int a = 1; a <= 32;){
   printf("%d\n", a);
   a = a*2;
}

Dalam pemograman di atas nilai n adalah 32 maka jumlah iterasi yang berlangsung adalah sebanyak log₂32 + 1 yaitu 5 + 1 = 6.