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)
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 solutionSolution 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 solutionSolution for (d)
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.
Unlock detailed solutionSolution 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 solutionSolution 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