[DM 2005/09]

[1/09] Które z poniższych zdań są prawdziwe?

(a) 5 + 1/x = O(1)

(b) xlog²x = o(x²logx)

(c) 2^x+2 = Ω(x2^x+1)

(d) x² + logx = o(x² + xlogx)

[2/09] Dla każdej pary dwóch z poniższych funkcji f i g odpowiedz, czy następujące związki są spełnione: f(x) = O(g(x)), f(x) = o(g(x)), f(x) = Ω(g(x)), f(x) = ϖ(g(x)), f(x) = θ(g(x)).

1. x → x²logx + (1 + 1/x)²

2. x → x³(1 - 1/x)log²x

3. x → 3(x + 2)^1/2 log³x

4. x → 1998

5. x → (1 + 3/x)^x

6. x → (logx / x)

[3/09] Czy dla dowolnych dwóch funkcji ciągłych f, g : R⁺ → R⁺ musi zachodzić co najmniej jeden z następujących związków: f (x) = O(g(x)), f(x) = Ω(g(x))?

[4/09] Czy dla dowolnych funkcji f, g takich, że f(x) = o(g(x)) można znaleźć funkcję h taką, że f(x) = o(h(x)) oraz h(x) = o(g(x))?

[5/09] Podaj przykład (o ile istnieje) funkcji f : N → R⁺ takiej, że:

1. f(n) = o(2n² + n + 1) ∧ f(n) = ω(2n ² - n - 1)

2. f(n) = o(n² + n + 1) ∧ f(n) = ω(n + 2003n + 1)

3. f(n) = o(2ⁿ + n²) ∧ f(n) = ω(n ² + logn)

4. f(n) = O(n) ∧ ∀_n∈N(f(n) > n)

5. f(n) = O(n²) ∧ ∀_n∈N(f(n) > 7n² + 2n)

6. f(n) = o(nlogn) ∧ f(n) = ω(n + 2003)

[6/09] Czy istnieje funkcja f : N → R⁺ taka, że:

1. ∀_a∈N(f(n) = ω(n^a)) ∧ ∀_a∈N(f(n) = o((1+1/a)ⁿ)

2. ∀_a∈N(f(n) = ω((lnn)^a)) ∧ ∀_a∈N(f(n) = o(n^1/a)

3. f(n) = ω(nⁿ)

[7/09] Uporządkuj podane funkcje w porządku rosnącego tempa wzrostu:

1. x + logx + x²

2. (0,5)^x + x/logx

3. 2002logx + x

4. xlogx + log⁴x

5. 2002x^1/2

---