Aloha :)
Für die erste Summe kannst du die geometrische Summenformel verwenden:$$\sum\limits_{k=0}^nq^k=\frac{q^{n+1}-1}{q-1}\quad\stackrel{(q=2)}{\implies}\quad\sum\limits_{k=0}^n2^{k}=\frac{2^{n+1}-1}{2-1}=2^{n+1}-1$$Damit ist dann$$\ln\left(\sum\limits_{k=0}^nq^k\right)=\ln\left(2^{n+1}-1\right)<\ln(2^{n+1})=(n+1)\cdot\ln(2)=\pink{O(n)}$$Die Zuordnung zu \(O(n)\) kannst du wie folgt begründen:$$\lim\limits_{n\to\infty}\left|\frac{(n+1)\cdot\ln(2)}{n}\right|=\lim\limits_{n\to\infty}\left|\frac{n\ln(2)+\ln(2)}{n}\right|=\lim\limits_{n\to\infty}\left|\ln(2)+\frac{\ln(2)}{n}\right|=\left|\ln(2)\right|<\infty$$
Für die zweite Summe betrachte:$$\sum\limits_{k=0}^n\binom{n}{k}^2=\sum\limits_{k=0}^n\binom{n}{k}\binom{n}{k}=\sum\limits_{k=0}^n\binom{n}{k}\binom{n}{n-k}=\binom{2n}{n}$$Das letzte Gleichheitszeichen sollte dir ohne Rechnung sofort klar sein:
\(\binom{2n}{n}\) ist die Anzahl der Möglichkeiten aus \(2n\) Objekten genau \(n\) auszuwählen. Diese \(2n\) Objekte teilst du bei der Summe in 2 Haufen zu je \(n\) Objekten auf. \(\binom{n}{k}\) ist die Anzahl der Möglichkeiten, aus den ersten \(n\) Objekten genau \(k\) auszuwählen und \(\binom{n}{n-k}\) ist die Anzahl der Möglichkeiten, aus den zweiten \(n\) Objekten genau \((n-k)\) auszuwählen. Unter der Summe werden also für jedes \(k\) stets \(n\) Objekte ausgewählt. Das \(k\) bestimmt, wie viele von den Objekten aus dem ersten Haufen genommen werden und \((n-k)\) bestimmt, wie viele davon aus dem zweiten Haufen genommen werden. Summiert gibt das die Anzahl der Möglichkeiten, aus allen \(2n\) Objekten genau \(n\) auszuwählen.
Zur Abschätzung der Laufzeit würde ich nun so vorgehen:$$4^n=2^{2n}=(1+1)^{2n}=\sum\limits_{k=0}^{2n}\binom{2n}{k}\cdot1^k\cdot1^{2n-k}\ge\binom{2n}{n}\quad\implies\quad\binom{2n}{n}=\pink{O(4^n)}$$
