Úkoly z Kombinatoriky a grafů, 1. série

Veškerá tvrzení precizně zdůvodněte.

(1.1) Na cvičení jsme správně seřadili do pořadí podle rychlosti asymptotického růstu tyto funkce:

n^{1+1/ log n} , n logn, n^{1+1/ log log n} , n^{2}, n^{2 log log n}

Dále jsme ukázali, že uvedené funkce se liší asymptoticky ostře (tj. jsou od sebe o(…)). Doplňte do této řady funkce

(loglogn)^{log n}, (logn)^{log log n}, ne^{\sqrt{log n}}, (logn)^{log n}

a pro všechny sousedy v této řadě uveďte, jak moc se aymptoticky liší, tj. jestli ostře nebo mají aymptoticky stejny odhad. 5 bodů

(1.2) Dokažte, že algoritmus Eratosthenova síta má časovou složitost O(n logn). (Mimo soutěž: Je to nejlepší možný odhad?) 3 body