Tegyük fel, hogy egy `n` elemű `x_1` tömböt akarsz rendezni `f(x)` függvénnyel. Legyen `x_2` egy `10n` elemű tömb. Jelöljük `f(x_1)` futási idejét `t`-vel.
Tudjuk, hogy `f(x)` algoritmus jellemezhető `O(n^2)`-tel. Ez azt jeleni, hogy `f(x_2)` futási idejét megközelítőleg `10^2t`-re várhatjuk, mivel `x_2`-nek 10-szer annyi eleme van.

Sajnos ez nem feltétlen működik így. Az `O()` jelölésben az algoritmusok komlexitását nagyon lecsupaszítják. Teszem én azt egy függvény komplexitására kiszámolod, hogy `3n^2+10n+621`, attól még `O(3n^2+10n+621)=O(n^2)`, mert a legnagyobb kitevő mérvadó.

Emellett ez az átlagos futási időt jellemzi. Azt, hogy egy rendező algoritmus mennyi idő alatt fut le, azt elég sok tényező befolyásolja. Az átlagos mellett szoktak jellemezni legjobb és legrosszabb esettel is.

Na de akkor mire jó ez, ha semmi konkrétat, de még csak megközelítőt is nehezen tud mutatni a futási időkről?
Erre a legjobb válasz, amit tudok adni, az az, hogy függvények futási idejének összehasonlítására nagyon nagy bemenet esetén. Ha van egy rendező függvényem, ami `O(n^2)` időkomplexitású, és egy másik, ami `O(nlogn)`, akkor ha beadok neki mondjuk egy 10 000 000 elemű tömböt, akkor az `O(nlogn)`-es gyorsabban fog végezni (ha mondjuk 100 elemnél megegyezett a futási idő).

Valószínűleg nem ez a legjobb magyarázat, amit valaha olvasni fogsz, de sajnos én sem ismerem olyan régóta ezt a jelölést, ezért nekem is nehezemre esik magyarázni. Emellett tényleg nagyban függ maguktól az algoritmusoktól, mivel ahogy írtam a fentebbi példában `n^2` az csak a teljes komplexitás leegyszerűsített változata, mivel ha `n` elég nagy, a többi úgyis elhanyagolható nagyságú lesz (kicsit mint a határértéknél). Szakkifejezéseket se igazán használtam, mivel angol informatikai segítséget és szakirodalmat sokkal könnyebben lehet találni a neten. Ajánlom, hogy keress rá, hogy "big o notation", és lesz jópár stackowerflow poszt, youtube videó, meg egyéb szakavatottabb források, amik sokkal pontosabbak és valószíűleg érthetőbbek nálam.
Ha valaki talál hibát abban amit írtam, vagy ír egy jobb választ, akkor írjon egy kommentet, hogy kapjak értesítést, mert engem is érdekel.