Aloha :)
Damit \(f(n)\in O(g(n)\) gilt, muss der Limes superior von \(\frac{f(n)}{g(n)}<\infty\) sein.
Dabei kann die Regel von L'Hospial \((\ast)\) oft weiterhelfen:
$$\small\lim\limits_{n\to\infty}\frac{\sqrt n}{\log(n)}\stackrel{(\ast)}{=}\lim\limits_{n\to\infty}\frac{\frac{1}{2\sqrt n}}{\frac1n}=\lim\limits_{n\to\infty}\frac{\sqrt n}{2}=\infty\implies\pink{\sqrt n\not\in O(\log n)}$$
$$\small\lim\limits_{n\to\infty}\frac{4n+5n}{4n}=\lim\limits_{n\to\infty}\frac{9n}{4n}=\lim\limits_{n\to\infty}\frac{9}{4}=\frac94<\infty\implies\pink{(4n+5n)\in O(4n)}$$
$$\small\lim\limits_{n\to\infty}\frac{2^n}{3^n}=\lim\limits_{n\to\infty}\left(\frac23\right)^n=0<\infty\implies \pink{2^n\in O(3^n)}$$
$$\small\lim\limits_{n\to\infty}\frac{\log(10^n)}{\log n}=\lim\limits_{n\to\infty}\frac{n\cdot\log(10)}{\log n}\stackrel{(\ast)}{=}\lim\limits_{n\to\infty}\frac{\log(10)}{\frac1n}=\lim\limits_{n\to\infty}(n\log(10))=\infty\implies\pink{\log(10^n)\not\in O(\log n)}$$
$$\small\lim\limits_{n\to\infty}\frac{\log_2(n)}{\log_{10}(n)}=\lim\limits_{n\to\infty}\frac{\frac{\ln(n)}{\ln(2)}}{\frac{\ln(n)}{\ln(10)}}=\lim\limits_{n\to\infty}\frac{\ln(10)}{\ln(2)}=\log_2(10)<\infty\implies\pink{\log_2(n)\in O(\log_{10}(n)}$$
Für die letzte Aufgabe wähle folgendes Gegenbeispiel:$$f(n)=n\;\text{und}\; g(n)=n\implies\operatorname{max}(f(n);g(n))=n$$$$\small\lim\limits_{n\to\infty}\frac{f(n)\cdot g(n)}{\operatorname{max}(f(n);g(n))}=\lim\limits_{n\to\infty}\frac{n^2}{n}=\lim\limits_{n\to\infty}(n)=\infty\implies\pink{f(n)\cdot g(n)\not\in O(\operatorname{max}(f(n);g(n)))}$$
