Duże O algorytmy Emilka: Wytłumaczy mi ktoś dlaczego n2ⁿ = O 3ⁿ oraz dlaczego 2ⁿ = ɵ 2ⁿ⁺¹

Adam: n2ⁿ∊O(3ⁿ) ponieważ ∀n>1 n2ⁿ≤3ⁿ

	1
2n∊Θ(2n+1) ponieważ		*2n+1≤2n≤2n+1
	2

Adam: popatrz na stronę https://pl.wikipedia.org/wiki/Asymptotyczne_tempo_wzrostu masz tam f(n)∊O(g(n)) jeśli od pewnego n zachodzi f(n)≤c*g(n) oraz f(n)∊Θ(g(x)) jeśli od pewnego n zachodzi c₁*g(n)≤f(n)≤c₂*g(n) gdzie c₁,c₂,c to wartości stałe

Emilka: Z innymi zadaniami tego typu mnie miałam problemów i ogólnie rozumiem tę notację ale nadal nie pojmuję jak 2ⁿ jest większe od 2ⁿ⁺¹ Przecież n+1 daje funkcję o jeden stopień większą. Tak samo moim zdaniem jest z n*2 i 3, pomijając stałe wyjdzie n i 1, przecież n powinno być większe niż 1.

Adam:

	3
masz n2n≤3n stąd n≤(		)n, a z tym się chyba zgodzisz, prawda?
	2

to jasne że funkcja wykładnicza rośnie szybciej niż liniowa co do 2ⁿ to zauważ że nikt nie mówi że 2ⁿ jest większa od 2ⁿ⁺¹ napisałem wcześniej

1		1
	*2n+1≤2n≤2n+1, gdzie		,1 to stałe
2		2

2⁻¹*2ⁿ⁺¹≤2ⁿ≤2ⁿ⁺¹ 2ⁿ≤2ⁿ≤2ⁿ⁺¹ oczywiście mamy 2ⁿ=2ⁿ więc 2ⁿ≤2ⁿ co do 2ⁿ≤2ⁿ⁺¹ raczej nie masz wątpliwości