Problem Big O Notation

Level 3 (with higher mathematics)
Level 3 requires the basics of vector calculus, differential and integral calculus. Suitable for undergraduates and high school students.

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)

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
Formula anchor

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.

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)

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
Formula anchor

Divide on both sides by $$n$$:

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

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
Formula anchor

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.

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
All content on the website is for free. However, since this project has to fund itself somehow, it relies on advertising revenue. Want to see the solutions? Please deactivate your AdBlocker!