# 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?

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

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

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

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

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

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

\(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**

## 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.

## 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.

## Solution for (d)

**n mal Logarithmus von 2 kleiner gleich c1 mal n Quadrat plus c2**

**Logarithmus von 2 kleiner gleich c1 mal n plus c2 durch n**

**n kleiner gleich 2 hoch c1 mal n**

n ~&\stackrel{?}{\leq}~ 2^{c_1 \, n} \end{align} $$

## 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.

## 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.

## 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.