Mein Ansatz wäre das ganze mit dem Master-Theorem zu lösen, allerdings hatte ich als Anfangswert T(1) bisher immer nur ganzzahlige Werte angegeben, wie gehe ich hier vor?
Ist der Startwert überhaupt so wichtig für das asymptotische Wachstum?
Ich kenne das Master-Theorem so:
Sei \( a \geq 1, c \geq 2, d \geq 0 \) und \( T(n) \) durch \(T(n)=a\cdot T\left(\frac{n}{c}\right)+f(n)\) für \(n>1\) und \(T(1)=d\) mit einer Funktion \( f: \mathbb{N} \rightarrow \mathbb{R}_{+} \) gegeben.
Für \( n=c^{k} \) (mit \( k \in \mathbb{N} \) ) wächst \( T(n) \) asymptotisch gemäß
\( T(n) \in\left\{\begin{array}{ll} \Theta\left(n^{\alpha}\right)=\Theta(f(n)) & \text { falls } f(n) \in \Theta\left(n^{\alpha}\right) \text { mit } a<c^{\alpha}, \\ \Theta\left(n^{\log _{c} a} \log n\right) & \text { falls } f(n) \in \Theta\left(n^{\alpha}\right) \text { mit } a=c^{\alpha}, \\ \Theta\left(n^{\log _{c} a}\right), & \text { falls } f(n) \in \Theta\left(n^{\alpha}\right) \text { mit } a>c^{\alpha} . \end{array}\right. \)
