Falls das Master-Theorem benutzt werden darf und es sich bei c um eine Konstante handelt:
$$\text{Seien }e,f,g\text{ natürliche Konstanten und }e\geq 0, f>0\text{ sowie }\\h: \mathbb{N}_0 \rightarrow \mathbb{R}\text{ eine asymptotisch positive Funktion.}$$
Für eine Rekursionsgleichung der Form $$T(n)=\begin{cases} \Theta(1), \ falls \ n\leq g \\ e\cdot T(\frac{n}{f})+h(n), \ sonst \end{cases}$$
kann T wie folgt asymptotisch abgeschätzt werden:
(1) $$h(n) \in O(n^{log_fe-\epsilon})\text{ für ein }\epsilon>0 \Rightarrow T(n)\in \Theta(n^{log_fe})$$
(2) $$h(n) \in \Theta(n^{log_fe}) \Rightarrow T(n)\in \Theta(n^{log_fe} \cdot \log (n))$$
(3) $$h(n) \in \Omega(n^{log_fe+\epsilon}) \text{ für ein } \epsilon>0 \text{ und gilt } e\cdot h(\frac{n}{f})\leq v\cdot h(n) \text{ für eine Konstante } \\v<1 \text{ und hinreichend große } n \text{, so gilt } T(n)\in \Theta(h(n))$$
In deiner Aufgabe wird dementsprechend Fall (2) genutzt, denn $$c\in \Theta(1) \\ h(n)=c\cdot n \in \Theta(n)=\Theta(n^{\log_{10}(10)})$$
$$\text{Daher folgt }T(n)\in \Theta(n \cdot \log(n))$$
Falls das Master-Theorem nicht angewendet werden darf Beweis z.B. über Rekursionsbaum führen.
Beweisskizze:
$$\text{Im Rekursionsbaum besitzt jeder Vater der Größe }n\text{ genau }10\text{ Kinder, die jeweils die Größe } \frac{n}{10} \text{ besitzen.} $$
$$\text{Da die Größe auf jeder Ebene gezehntelt wird und der Basisfall für }\\ T(n)\leq 1 \text{ gegeben ist, beträgt die maximale Stufenzahl } s \text{ des Baumes } \frac{n}{10^s}=1 \Rightarrow s=\log_{10}(n)$$
$$\text{Bei einer Größe von } \frac{n}{10^i} \text{ und } 10^i \text{ Kindern }\text{ auf jeder Stufe } i \text{ des Baumes ergibt sich je ein Aufwand von }\\ \frac{n}{10^i} \cdot 10^i=n$$
$$\text{Insgesamt ergibt sich zumindest eine obere Grenze des Gesamtaufwandes von } \\T(n)\leq\log_{10}(n)\cdot n \in O(n\cdot \log(n))$$
