\input dmmac

\serie1

\task
Na cvi�en� jsme spr�vn� se�adili do po�ad� podle rychlosti asymptotick�ho r�stu
tyto funkce:
$$
n^{1+1/\log n},\quad n\log n,\quad n^{1+1/\log\log n},\quad n^2,\quad n^{2\log\log n}
$$
D�le jsme uk�zali, �e uveden� funkce se li�� asymptoticky ost�e (tj. jsou od sebe $o(\dots))$.
Dopl�te do t�to �ady funkce
$$
(\log\log n)^{\log n},\quad (\log n)^{\log\log n},\quad ne^{\sqrt{\log n}},\quad (\log n)^{\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.
\body5

\task
Doka�te, �e algoritmus Eratosthenova s�ta m� �asovou slo�itost $O(n\log n)$.
(Mimo sout�: Je to nejlep�� mo�n� odhad?)
\body{3}


\bye

