0 Daumen
339 Aufrufe

Aufgabe:
Für alle p,q ∈ N mit p < q, ist O(np) ⊊ O(nq).


Problem/Ansatz:

Beweisen Sie

Avatar von

1 Antwort

0 Daumen
Für alle p,q ∈ N mit p < q, ist O(np) ⊊ O(nq).

Das ist sicherilch nicht der Fall.

\(\begin{aligned}f \in O(nq)&\implies \exists c\in (0,\infty)\ \exists N\in \mathbb{N}\ \forall n>N:\ f(n)\leq c \cdot nq\\&\implies \exists c\in (0,\infty)\ \exists N\in \mathbb{N}\ \forall n>N:\ f(n)\leq c \cdot np\cdot \frac{q}{p}\\&\implies \exists c\in (0,\infty)\ \exists N\in \mathbb{N}\ \forall n>N:\ f(n)\leq \frac{qc}{p} \cdot np\\&\implies \exists c\in (0,\infty)\ \exists N\in \mathbb{N}\ \forall n>N:\ f(n)\leq c \cdot np\\&\implies f\in O(np)\end{aligned}\)

Avatar von 105 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community