I have the following problem:
Order the following functions in increasing order of asymptotic (big-O) complexity.
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!
On
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)$$
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})$.