Wie zeigt man folgende Funktion als O-Notation?

Question

Aufgabe:

Text erkannt:

b) Gegeben $f(n)=\log \left(n^{2}\right)$, zeigen Sie: $f(n)=O(\log (n))$

Answer 1

Hallo :-)

Du musst doch noch ein Logarithmusgesetz hier anwenden:

$f(n)=\log(n^2)=2\cdot \log(n)$

Mit $n_0=1$ und $\alpha=2$ ist also für alle $n\geq 1$

$0\leq f(n)=\alpha\cdot \log(n)$

Gleiche das mal mit der Definition zur O-Notation ab:

Es sei $g: \mathbb{N}\rightarrow \mathbb{R}$. Dann ist$$\mathcal{O}(g):=\{f:\ \mathbb{N}\rightarrow \mathbb{R}:\ \exists \alpha>0 \ \exists n_0 \in \mathbb{N} \ \forall n\geq n_0:\ \underbrace{0\leq f(n) \leq \alpha \cdot g(n)}_{0\leq f(n) \ \land f(n)\leq \alpha\cdot g(n) } \}$$

Answer 2

Hallo,

log(n²) = 2log(n) und das ist Element von O(log(n)).