Príklad 2. Zoberme si konkrétny program – implementáciu jednoduchého triedenia MinSort.
for i in range(n):
for j in range(i+1, n):
if A[i] > A[j]:
A[i], A[j] = A[j], A[i] # vymeň A[i] a A[j]
Ak by nám niekto povedal konkrétny vstup, ktorý tento algoritmus dostane
(v našom prípade teda hodnotu $n$ a obsah poľa A), vedeli by sme presne
spočítať počet krokov, ktoré náš algoritmus spraví. Dokonca by sme
vedeli presne povedať počet inštrukcii, ktoré vykoná procesor počas jeho
behu. Takýto prístup však nie je veľmi praktický, keďže v praxi je
možných vstupov priveľa a nemôžeme ich vyskúšať všetky.
Čo presne nás teda bude zaujímať? Sú nejaké "dôležité" vstupy, na ktoré sa stačí pozrieť, alebo ako? Väčšinou to, čo budeme chcieť zistiť, bude dĺžka behu programu v najhoršom možnom prípade. Hm, čo je to ale najhorší možný prípad? Veď určite môžeme program donútiť bežať aj dlhšie – jednoducho tak, že mu dáme väčší vstup...
Už zmysluplnejšie otázky sú nasledovné: Spomedzi všetkých vstupov so 700 prvkami, na ktorom pobeží náš program najdlhšie? Ako dlho to bude? Ako rýchlo rastie tento potrebný čas v závislosti od počtu prvkov, resp. od veľkosti vstupu?