# Problem Big O Notation

Here, the asymptotic growth behavior of various functions must be investigated, which could, for example, describe the runtime of an algorithm. Which of the following statements is true and which is false?

1. $$42n + 8 ~\stackrel{?}{\in}~ \mathcal{O}(n)$$

2. $$3^n ~\stackrel{?}{\in}~ 2^{\mathcal{O}(n)}$$

3. $$5n^3 ~\stackrel{?}{\in}~ 2^{\mathcal{O}(n)}$$

4. $$n \, \log_2 (n) ~~\stackrel{?}{\in}~ \mathcal{O}(n^2)$$

5. $$n^4 ~\stackrel{?}{\in}~ \mathcal{O}(n^3 \, \log_2 (n))$$

6. $$6\,n^4 + 7n^3 + 18 ~\stackrel{?}{\in}~ \mathcal{O}(n^5)$$

7. $$n \, \log_2(n) + n^2 \, \sqrt{n} ~\stackrel{?}{\in}~ \mathcal{O}(n^4)$$

Solution tips

Use the definition of the Big O symbol:$\mathcal{O}(f) ~=~ \{~g ~|~ \exists \, c_1, c_2 > 0, \forall n \in \mathbb{N}: g(n) \leq c_1 \, f(n) + c_2~\}$and consider the inequalities:$g(n) ~\leq~ c_1 \, f(n) + c_2$

## Exercise solutions

Solution for (a)
Ungleichung 1
Formula anchor
Solution for (b)

The statement $$3^n ~\in~ 2^{\mathcal{O}(n)}$$ is true!

To see a detailed solution, you need to unlock this feature first.

Unlock detailed solution
Solution for (c)

The statement $$5n^3 \in 2^{\mathcal{O}(n)}$$ is true!

To see a detailed solution, you need to unlock this feature first.

Unlock detailed solution
Solution for (d)
n mal Logarithmus von 2 kleiner gleich c1 mal n Quadrat plus c2
Formula anchor
Logarithmus von 2 kleiner gleich c1 mal n plus c2 durch n
Formula anchor
n kleiner gleich 2 hoch c1 mal n
Formula anchor
Solution for (e)

The statement $$n^4 \not\in \mathcal{O}(n^3\,\log_2(n))$$ is true!

To see a detailed solution, you need to unlock this feature first.

Unlock detailed solution
Solution for (f)

The statement $$6\,n^4 + 7n^3 + 18 \in \mathcal{O}(n^5)$$ is true!

To see a detailed solution, you need to unlock this feature first.

Unlock detailed solution
Solution for (g)

The statement $$n \, \log_2(n) + n^2 \, \sqrt{n} ~\in~ \mathcal{O}(n^4)$$ is true!

To see a detailed solution, you need to unlock this feature first.

Unlock detailed solution