Pre skoro všetky algoritmy, ktoré v praxi stretneš, bude konštanta "skrytá za $O$, resp. $\Theta$" rozumne malá. Teda ak nejaký algoritmus je $\Theta\left( N^2 \right)$, môžeš čakať, že jeho presná časová zložitosť je napríklad $10N^2$, a nie $10^7 N^2$.
To isté pozorovanie z opačnej strany: Ak je tá konštanta náhodou veľká, je to väčšinou preto, že nejako súvisí s konštantami uvedenými v zadaní úlohy. V takomto prípade sa patrí tú konštantu nejako nazvať a uvádzať ju v asymptotickom odhade.
Napríklad majme problém: Zadaný je reťazec dĺžky $N$, spočítaj pre každé písmeno, koľkokrát sa v ňom vyskytuje. Jeden možný algoritmus je pre každé písmeno raz prejsť celý reťazec a spočítať jeho výskyty. Rôznych znakov je najviac $255$, takže tento algoritmus je lineárny od dĺžky reťazca. Ale napriek tomu je lepšie zapísať jeho zložitosť ako $\Theta\left( | S | \cdot N \right)$, kde $S$ je množina znakov, ktoré sa môžu v reťazci vyskytnúť. (Ľahko zistíme, že existuje aj lepší algoritmus, ktorý túto úlohu rieši v čase $\Theta\left( | S | + N \right)$.)
Na priemernom súčasnom počítači potrebuje program, ktorý počíta $1\,000\,000\,000$ násobení celých čísel, niekoľko sekúnd. Na základe tejto skúsenosti vieme odhadnúť, aký veľký vstup dokáže náš algoritmus v rozumnom čase vyriešiť, ak poznáme jeho časovú zložitosť. Približné odhady sú v nasledujúcej tabuľke:
| zložitosť | najväčšie N |
|---|---|
| $\Theta\left(N\right)$ | $100\,000\,000$ |
| $\Theta\left(N\log N \right)$ | $4\,000\,000$ |
| $\Theta\left(N^2 \right)$ | $10\,000$ |
| $\Theta\left(N^3 \right)$ | $500$ |
| $\Theta\left(N^4 \right)$ | $90$ |
| $\Theta\left(2^N \right)$ | $20$ |
| $\Theta\left(N! \right)$ | $11$ |
Tabuľka 3. Približné maximálne veľkosti vstupu, ktorý sa dá vyriešiť za pár sekúnd.