Skip to main content

Problem Big O Notation

O Notation (Landau Symbol) - Growth Behavior
Level 3 (with higher mathematics)
Level 3 requires the basics of vector calculus, differential and integral calculus. Suitable for undergraduates and high school students.
O Notation (Landau Symbol) - Growth Behavior
Different growth rates.

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