Samozrejme, nikto neočakáva, že hneď pochopíte, čo to vlastne znamená. Postupne sa však s $O$-notáciou budete stretávať neustále. Práve v nej sa totiž neustále vyjadruje časová aj pamäťová zložitosť všetkých algoritmov. My si ukážeme pár funkcií, s ktorými sa stretnete najčastejšie.
Ešte sme si však nepovedali, na ktorom vstupe rátame zložitosť. Môže sa totiž stať, že niekde bude náš program potrebovať len $O(n)$ operácií a inde zase $O(n^2)$. V tomto prípade samozrejme berieme do úvahy najhorší možný príklad a zložitosť výpočtu na ňom prehlásime za zložitosť riešenia.
Ďalšia vec je, že my informatici sme tak trochu flákači. Vyjadrovanie sa v $O$-notácii je totiž mierne nepresné. Ako sme totiž ukazovali, tak $n^2 = O(n^3)$. Ak máme teda algoritmus so zložitosťou $f(n)$, nič nám nebráni povedať, že to je vlastne $O(n^3)$. Nás však zaujíma takpovediac najmenšia dolná hranica, v tomto prípade $n^2$. Takúto zložitosť by ste mali udávať aj všade, kde po vás požadujú zložitosť.