$(20$ points$)$ Question $3$

For each group of functions, sort the functions in increasing order of asymptotic $($big$-$O$)$

complexity, and explain your answer.

Note: "increasing order" refers to arranging the functions from the one that grows at the

slowest rate to the one that grows at the fastest rate. In other words, it means placing the

functions in ascending order based on how quickly their time complexity increases as the input

size grows.

Group $1$:

$f_1(n)=O(2^n)$

$f_2(n)=O(n!)$

$f_3(n)=O(n^3)$

$f_4(n)=O(n^2)$

$f_5(n)=O(nlogn)$

Group $2$:

$f_1(n)=2^{2^{1000000}}$

$f_2(n)=2^{100000n}$

$f_3(n)=([n$

$2])$

$f_4(n)=n\sqrt[\phantom{2}]{n}$

Search $"$n choose $2"$ if you are not

familiar with this mathematical

expression