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 \\ 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 a+b\left\lfloor\log _{2}(n)\right\rfloor \) für alle \( n \in \mathbb{N}_{>0} \) gilt.
