1

$f,g: \mathbb{N}_0 \rightarrow \mathbb{N}^+.$

$ f(n)^{O(g(n))}$ is the set of functions $h: \mathbb{N}_0 \rightarrow \mathbb{R}_0^+$ with $h(n) = f(n)^{k(n)}$ for a $k \in O(g).$

Explain whether these statements are true or false.

a) $n + O(n) = O(n+n)$

b) $O(n^1) = n^{O(1)}$

c) $O(2^n) = 2^{O(n)}$

I tried to understand these equations.

a) for any function $p(n) \in O(n)$ there is a function $q(n) \in O(n+n)$ so that $n + p(n) = q(n)$

$p(n) \leq c*n$ and $q(n) \leq c'*(n+n)$

b)for any function $p(n) \in O(n^1)$ there is a function $q(n) \in O(1)$ so that $p(n) = n^{q(n)}$

$p(n) \leq c * n$ and $q(n) \leq c'*1$

c)for any function $p(n) \in O(2^n)$ there is a function $q(n) \in O(n)$ so that $p(n) = 2^{q(n)}$

$p(n) \leq c*2^n$ and $q(n) \leq c' * n$

Is this correct so far? How do I go on from here?

franz3
  • 449
  • 3
  • 11
  • Are these “$=$” actual set equalities, or merely inclusions? – Aphelli Jan 20 '20 at 12:35
  • I didn't know myself so I did as per Wikipedia. Wikipedia --> Big O Notation --> Matters of Notation --> Multiple uses – franz3 Jan 20 '20 at 13:25
  • Wikipedia quote: "In this use the "=" is a formal symbol that unlike the usual use of "=" is not a symmetric relation." – franz3 Jan 20 '20 at 13:28
  • This is supposed to be a school problem (that even recalls that $O(\cdot)$ are sets), not a series of practical calculations serving some purpose. It wouldn’t be unexpected to have one nitpick the meanings of the symbols. Anyway, with your interpretation, every last sentence of your explanation is redundant with what you already wrote to define the functions. In b) and c), the equality after “so that” is probably not what you intended to write. – Aphelli Jan 20 '20 at 15:21

0 Answers0