1. Übungsblatt

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