Misalkan \(f:\posints\longrightarrow \reals\) dan \(g:\posints\longrightarrow\reals\) merupakan fungsi bernilai tak negatif. Kita menulis \(f=O(g)\text{,}\) dan mengatakan bahwa \(f\) berorde “O besar” terhadap \(g\text{,}\) jika terdapat konstanta positif \(c\) dan bilangan bulat \(n_0\) sedemikian sehingga \(f(n)\le cg(n)\) setiap kali \(n>n_0\text{.}\) Walaupun notasi ini memiliki sejarah panjang, kita dapat memberikan pembenaran yang cukup modern. Jika \(f\) dan \(g\) sama-sama menyatakan banyaknya operasi yang diperlukan oleh dua algoritma untuk masukan berukuran \(n\text{,}\) maka \(f=O(g)\) berarti bahwa algoritma yang diukur oleh \(f\) tidak lebih sulit daripada algoritma yang diukur oleh \(g\) ketika ukuran masalahnya besar.
Kita terutama berkepentingan membandingkan fungsi dengan sejumlah tolok ukur alami, e.g., \(\log\log n\text{,}\)\(\log n\text{,}\)\(\sqrt{n}\text{,}\)\(n^\alpha\) dengan \(\alpha\lt 1\text{,}\)\(n\text{,}\)\(n^2\text{,}\)\(n^3\text{,}\)\(n^c\) dengan \(c>1\) suatu konstanta, \(n^{\log n}\text{,}\)\(2^n\text{,}\)\(n!\text{,}\)\(2^{n^2}\text{,}\) etc.
Sebagai contoh, dalam Subbagian 3.5.2 kita telah mempelajari adanya algoritma pengurutan dengan waktu berjalan \(O(n\log n)\text{,}\) dengan \(n\) menyatakan banyaknya bilangan bulat yang akan diurutkan. Sebagai contoh kedua, nanti kita akan mempelajari bahwa semua jalur terpendek dari satu simpul akar ke setiap simpul lain dalam graf berorientasi dengan \(n\) simpul dan bobot tak negatif pada sisi-sisinya dapat ditemukan oleh algoritma dengan waktu berjalan \(O(n^2)\text{.}\) Pada ekstrem lainnya, belum diketahui apakah terdapat konstanta \(c\) dan algoritma dengan waktu berjalan \(O(n^c)\) untuk menentukan apakah bilangan kromatik suatu graf paling banyak tiga.
Penting untuk diingat bahwa ketika kita menulis \(f=O(g)\text{,}\) dalam arti tertentu kita menyiratkan bahwa \(f\) tidak lebih besar daripada \(g\text{,}\) tetapi sebenarnya fungsi tersebut mungkin jauh lebih kecil. Sebaliknya, ada kalanya kita benar-benar mengetahui bahwa satu fungsi mendominasi fungsi lainnya. Untuk menyatakan hubungan ini, kita memiliki jenis notasi kedua.
Misalkan \(f:\posints\longrightarrow \reals\) dan \(g:\posints\longrightarrow\reals\) merupakan fungsi dengan \(f(n)>0\) dan \(g(n)>0\) untuk setiap \(n\text{.}\) Kita menulis \(f=o(g)\text{,}\) dan mengatakan bahwa \(f\) berorde “o kecil” terhadap \(g\text{,}\) jika \(\lim_{n\rightarrow\infty}f(n)/g(n)=0\text{.}\) Sebagai contoh, \(\ln n=o(n^{.2})\text{;}\)\(n^\alpha=o(n^{\beta})\) setiap kali \(0\lt \alpha\lt \beta\text{;}\) dan \(n^{100}=o(c^n)\) untuk setiap \(c>1\text{.}\) Secara khusus, kita menulis \(f(n)=o(1)\) ketika \(\lim_{n\rightarrow\infty}f(n)=0\text{.}\)
