Notacja ${\mathcal O}(\cdot)$

Złożoność obliczeniowa określa to największą ilość kroków potrzebnych do wykonania algorytmu. Ze względu na różne architektury komputerów etc. trudno jest podać ogólną definicję ,,kroku''. W rozważaniach podstawowych wystarczająca jest analiza wzrostu złożoności obliczeniowej z rozmiarem problemu, czyli danych wejściowych. Opisuje ją notacja ${\mathcal O}(\cdot)$. Złożoność ,,bezmyślnego'' przeszukiwania listy długości $N$: ${\mathcal O}(N)$. Przeszukiwanie binarne - ${\mathcal O}\left(\log_2(N)\right)$.