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

The statement \( 42n + 8 ~\in~ \mathcal{O}(n) \) is true, because with \( g(n) = 42n \) and \(f(n) = n \), according to the definition of the Big O Symbol we get:

**42 times n plus 8 less than or equal to c1 times n plus c2**

Hierbei sind die Koeffizienten: \(c_1 ~\geq~ 42, c_2 ~\geq~ 8\).

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

With \( g(n) = n\,\log_2(n) \) and \(f(n) = n^2 \) according to the definition of the big O symbol:

**n times log of 2 less than or equal to c1 times n squared plus c2**

Divide on both sides by \(n\):

**Logarithm of 2 less than or equal to c1 times n plus c2 divided by n**

The inequality is satisfied if the following equation is satisfied (because \(\frac{c_2}{n} \geq 0 \)):

**n less than or equal to 2 to the power of c1 times n**

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

Since the inequality is satisfied, \( n\,\log_2(n) \in \mathcal{O}(n^2) \) is true.

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

**Please deactivate your AdBlocker!**