Seien a;b 2 N>0 gegeben und sei T : N>0 !N>0 eine Abbildung

Question

Aufgabe:

Seien \( a, b \in \mathbb{N}_{>0} \) gegeben und sei \( T: \mathbb{N}_{>0} \rightarrow \mathbb{N}_{>0} \) eine Abbildung mit

$$ T(n) \leq\left\{\begin{array}{ll} a & \text { falls } n=1 \\ n+b+T(\lfloor n / 2\rfloor) & \text { sonst } \end{array}\right. $$

für alle \( n \in \mathbb{N}_{>0} \). Zeigen Sie, dass

$$ T(n) \leq 2 n+a+b\left\lfloor\log _{2}(n)\right\rfloor $$

für alle \( n \in \mathbb{N}_{>0} \) gilt.

Hinweis: In dieser Aufgabe kann nicht das Mastertheorem verwendet werden.