Notacja O Michał: Sprawdź czy podana równość jest prawdziwa czy fałszywa: log₂nⁿ = O(log₂n) log₂nⁿ ≤ C * log₂n Co mogę dalej zrobić z tymi logarytmami?

kochanus_niepospolitus: log₂nⁿ = n*log₂n <−−− własności logarytmów

Michał: Czyli: n * log₂n ≤ C * log₂n n ≤ C Podana równość jest fałszywa

Michał: A jak rozbić (2n)! = O(n!)?

Adamm: (2n)!∊O(n!) jeśli istnieje taka stała c że (2n)!≤c*n! od pewnego n czyli inaczej (2n)*(2n−1)*...*(n+1)≤c ale (2n)*(2n−1)*...*(n+1) rośnie nieograniczenie więc taka stała nie istnieje

Adamm: przy czym c>0, ale to mniejsza

Michał: Czyli tak naprawdę wystarczy od ciągu (2n)! odjąć n!, co przejawia się tym, że ostatnim wyrazem jest n+1? Dziękuję bardzo za pomoc, dobrego dnia życzę.

Adamm: podzielić nie odjąć

(2n)!
	=(2n)*(2n−1)*...*(n+1)
n!

Michał: Fakt, głupi błąd.