Potenzen als Teil einer Ungleichung umformen für Laufzeitanalyse

Question

Guten Abend Mathelounge,
im Rahmen von Laufzeitanalysen als Teil meiner Algorithmik-Forlesung ist folgende Ungleichung aufgetaucht die umgeformt wurde um weiter zu argumentieren:

Aus (n+a)^b ≤ C n^b folgt für n > 0 und b > 0:

$$ \frac{(n+a)^b}{n^b} \leq C   $$
Vereinfachen wir den Term, dann erhalten wir für n>0

(1+ \( \frac{a}{n} \))^b ≤C

Problem/Ansatz:

Mir ist nicht klar was bei dieser Umformung geschieht bzw. wie man von Ungleichung 1 zu Ungleichung 2 kommt. Mein Ansatz war mit n^-b / n^-b zu erweitern um im Nenner auf 1 zu kommen und dann weiter umzuformen, allerdings ist da das a in der Summe im Nenner "im Weg".

Kann mir jemand helfen?

Answer 1

Potenzgesetze und den Bruch auseinanderziehen: \(\frac{(n+a)^b}{n^b}=\left(\frac{n+a}{n}\right)^b=\left(\frac{n}{n}+\frac{a}{n}\right)^b\).

Comments

Danke sehr!!