1. Übungsblatt
Aus Tudwiki
Aufgabe 1.1 (Theta und Omega Notation)
(i) Geben Sie zu den nachstehenden Funktionen f_i: N->N eine möglichst einfache Funktion g_i:N->N an, so dass f_i = Theta(g_i(n)).
- 1. f_1(n) = 2(n+1)^2 + 3n -4
- C_1*g_1(n) <= f_1(n) <= C_2*g_1(n) für alle n >= n_0.
- => g_1(n) = n^2
- C_1*n^2 <= 2n^2 + 7n -2
- wenn C_1 = 2
- -> 0 <= 7n -2
- 2 <= 7n
- 2/t <= n => für alle n >= 1 => n_0 = 1
- 2n^2 + 7n -2 <= C_2*n^2
- ->C_2 = 3
- n^2 -7n +2 >= 0
- => n_0 = 7
- => n_0 = max(1,7) = 7
- 2n^2 + 7n -2 <= C_2*n^2
