notacja asymptotyczna iteRacj@: Wskaż, które oszacowania są poprawne. Proszę o sprawdzenie. (2ⁿ + n²)*log (nⁿ) = O(log (n²)) błędne (n!)² = O((n + 1)²ⁿ) poprawne n²*lg n = O(n² − n) poprawne

Adamm: ostatnie jest błędne

iteRacj@:

	n2*lg n		lg n
limn→∞		= limn→∞		= ∞
	n2 − n		1 − 1/n

więc n²*lg n = Ω(n² − n) ?

Adamm: n²*log(n) = O(n²−n) kiedy istnieje stała c i N że n²*log(n) ≤ c*(n²−n) dla n≥N innymi słowy

n2log(n)
	jest ograniczone
n2−n

Adamm: tak, n²log(n) = Ω(n²−n) (pewnie masz na myśli log₂(n), ale nie mam pewności)

iteRacj@: logarytm dziesiętny, ale zależność taka sama, tak?

Adamm: no, mnożysz przez jakąś stałą, wiele nie zmienia

iteRacj@: dzięki za wytłumaczenie!