Vždycky, když máš cyklus v cyklu, tak je to O(n2). Samozřejmě předpokládám, že ta funkce s lineární složitostí souvisí s tím samým počtem prvků (n) jako tento cyklus.
Samozřejmě jak tu již David psal, mělo by se jednat o funkci, která by byla závislá na prvku (n), což by byla, neboť jsem potřeboval v kolekci o délce (n) najít určitý prvek, což je již samo o sobě lineární hledání a mělo by to vyjít v tom foru na těch O(n2),
for (i = 0; i < 20; ++i)
for (j = 0; j < 20; ++j)
proved_nejakou_konstantni_operaci();tento kus kódu nebude nijak ovlivňovat asymptotickou složitost programu, protože počet operací, které provede, nezávisí na délce vstupních dat. Asymptotická složitost tohoto kusu je tedy O(1).
Zároveň je třeba mít na paměti, že asymptotická složitost obvykle nefunguje na malých vstupních datech. Pokud budeš třeba chtít seřadit 3-5 čísel, nemá smysl na tento úkol používat některý ze sofistikovaných třídících algoritmů ((randomizovaný) quicksort, heapsort), protože než se rozjedou, primitivní třídění založené na manuálním porovnávání je porazí.
Je to prostě jen takový horní odhat, kterým říkáš, že tvůj program pro rozumně velká vstupní data nepoběží pomaleji než ten výraz v závorce za O.
Děkuji za velice srozumitelnou odpověď, která mě zase obohatila o
znalosti a pár věcí vysvětlila 
Díky
Zobrazeno 7 zpráv z 7.