Materi
Notasi O besar menamai bagaimana jumlah langkah tumbuh ketika data bertambah. Ia tidak menyebut detik, tidak menyebut merek komputer, dan tidak menyebut angka pasti. Yang ditanyakan hanya satu: kalau datanya dua kali lebih banyak, langkahnya jadi berapa kali lipat? Faktor tetap dan bagian yang tumbuh lebih pelan dibuang, karena bagian yang tumbuh paling cepatlah yang menentukan nasib kode pada data besar.
| Nama | Data dua kali lipat | Contoh |
|---|---|---|
| O(1) | langkah tetap | mengambil isi list lewat indeks |
| O(log n) | bertambah satu langkah | pencarian biner pada daftar urut |
| O(n) | dua kali lipat | menelusuri seluruh daftar sekali |
| O(n log n) | sedikit di atas dua kali lipat | mengurutkan daftar |
| O(n²) | empat kali lipat | membandingkan setiap pasangan data |
Notasi ini dipakai dokumentasi Python sendiri. Halaman modul bisect menyebut bahwa pencarian O(log n) miliknya tertutupi oleh langkah penyisipan O(n), sehingga insort secara keseluruhan berbiaya O(n). Kalimat itu memperlihatkan cara memakai notasinya: ketika dua bagian digabung, yang tumbuh paling cepat yang dipakai menamai keseluruhannya.
