1

I have the following problem:

Order the following functions in increasing order of asymptotic (big-O) complexity.

enter image description here

I'm not entirely sure how they got to the answer though. I seem to be getting a few correct in a row, but still overall unsure about this. Any explanation would help. Thanks!

jjones5
  • 21
  • For typing math: MathJax –  Jul 17 '20 at 19:37
  • calculate $g(n)$, then replace constants by a letter, for instance comparing $f(n)=c_1$ and $p(n)=c_2n$ is made easier. You can also divide one by the other to compare them. – zwim Jul 17 '20 at 19:52
  • 1
    Your source using $q(x)$ instead of $q(n)$ is an unfortunate typo. But if @allesia_b's call to rewrite it in MathJax is ever heeded, that can be fixed. – J.G. Jul 17 '20 at 19:55
  • @J.G. lol...... –  Jul 17 '20 at 19:59

2 Answers2

1

Just use the ordering rule constant-linear-(higher-order-polynomial)-exponential-(faster-exponential), where the exponentials don't care about polynomial factors. The given order is correct viz.$$f\in O(1),\,p\in O(n),\,g\in O(n^2),\,q\in O(n2^{n/2}),\,h\in O(2^n)$$because $n\in o(2^{n/2})$.

J.G.
  • 115,835
0

Intuitively O-big is some type of "intellectual" extension of inequality. Exact definition $$O(g) = \left\lbrace f:\exists C > 0, \exists N \in \mathbb{N}, \forall n (n > N \& n \in \mathbb{N}) (f(n) \leqslant C \cdot g(n)) \right\rbrace$$ As we see, formally O-big is set of functions and "increasing order of asymptotic (big-O) complexity", here mean showing which function is in more large set, then another.

So, let's take first one $f(n) = 2^{2^{1000}}$. It is constant in respect with $n$, so it belongs to set $O(1)$ - set of bounded sequences, $f \in O(1)$.

Function $p(n) = 10^{10}n \in O(n)$ and as $O(1) \subset O(n) $, then the order between $f$ and $p$ is found. It is possible to write following chain $$f \in O(f) = O(2^{2^{1000}}) = O(1) \subset O(n) = O(10^{10}n) \ni 10^{10}n$$ Interesting exercise is to show, that equalities in above line is equalities between sets i.e. works in both direction.

Analogically we can write full requested order $$O(2^{2^{1000}}) \subset O(10^{10}n) \subset O\left(\sum_{i=1}^{n}(i+1) \right) \subset O\left(n2^{n/2} \right) \subset O\left(2^n \right)$$

zkutch
  • 13,410