Ahoj, potreboval bych pomoc s nejakymi priklady, ktere se pravdepodobne obevi v testu a ja si s nimi nevim rady.
(a) Rozhodnete jetli plati: 2ⁿ = Θ (3ⁿ). Vasi odpoved zduvodnete.
-Vim ze to neplati, ale nevim jak to mam dokazat. Muzu to rezepsat (2/3)^n<c a (2/3)^n>d , ale co s tim dal.
(b) Rozhodnete jetli plati: log n! = Θ (n log n). Vasi odpoved zduvodnete.
-O tomhle ze cviceni vim ze plati, ale opet nevim jak to mam dokazat.
(c) Uvedte priklad funknce, ktera roste (asymptoticky) rychleji nez f (n) = n a pritom pomaleji nez g (n) = n log n.
-Napada me jedine n*log(sqrt(n)) ale to de prepsat na 1/2*n*log(n) a to by melo rust stejne rychle jako n*log(n).
(Θ znamena stejny asymptoticky rust)
Offline