0 Daumen
251 Aufrufe

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.

von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

2 Antworten
Gefragt 1 Apr 2015 von Gast
1 Antwort
Gefragt 29 Nov 2015 von Gast
0 Antworten
0 Antworten
Gefragt 11 Nov 2014 von Gast

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community