Question

Prove or disprove the following: 

1. lg√n ∈ O(lg n) (√n means square root of n)

2. lg n ∈ O(lg√n) 

3. 2n+1 ∈ O(2n)


Answer 1

Answer on Question #85287 - Programming & Computer Science - Algorithms

Question 85287:

Prove or disprove the following:

1. $\log \sqrt{n} \in O(\log n), (\sqrt{n}$ means square root of $n$ )

2. $\log n\in O\bigl (\log \sqrt{n}\bigr)$

3. $2n + 1 \in O(2n)$

Answer:

Def.: $f(n) = O\big(g(n)\big) \Leftrightarrow \exists n_0 \in \mathbb{N}, \exists c \geq 0, \forall n \geq n_0, |f(n)| \leq c * g(n)$

1. $\left| \log \sqrt{n} \right| = \left| 1 / 2 \log n \right| \leq 1 * \log n, \forall n \in \mathbb{N}$

2. $|\log n| = \left|2\log \sqrt{n}\right|\leq 4*\log \sqrt{n},\forall n\in \mathbb{N}$

3. $|2n + 1| \leq |2n| + |1| < 4 * n, \forall n \in \mathbb{N}$

Answer provided by https://www.assignmentexpert.com