Activity $1.$

The goal of the activity is to enable students to discuss the concept of growth rate, and growth order$/$asymptotic order, recall the definition of big O notation and evaluate the asymptotic order of seven growth functions.

Task $1$ Which statements are correct about these following seven runtime functions :

T$($N$)=999$

T$($N$)=$ log$2$N

T$($N$)=$ N

T$($N$)=$ N $+999$

T$($N$)=5*$ N

T$($N$)=$ N $*$ log$2$N

T$($N$)=$ N$2$

Hints:

$1)$ The order of a function describes how the function scales as the input$($s$)$ increases to infinite. Seven typical functions are in an increasing order:

asymptotic$\_$order.jpg$.$png

$2)$ If the growth rates of two functions are the same, these two functions belong to the same time complexity group, denoted as in the big O notation:

For example, $($T$1(2$N$)/$T$1($N$))/(2$N$/$N$)=($T$2(2$N$)/$T$2($N$))/(2$N$/$N$)$ when T$1=5$N and T$2=$ N

or

$($T$3(2$N$)-$T$3($N$))/(2$N$/$N$)=($T$2(2$N$)-$T$2($N$))/(2$N$/$N$)$ when T$3=$ N$+999$ and T$2=$ N

or plot$/$tabulate it

O$(1)$ O$($logN$)$ O$($N$)$ O$($Nlog N$)$ O$($ N$2)$

N Alg. A T$($N$)=999$ Alg. B T$($N$)=$log$2$N Alg. C T$($N$)=$N Alg. D T$($N$)=$N$+999$ Alg. E T$($N$)=5*$N Alg. F T$($N$)=$Nlog$2$N Alg. G T$($N$)=$N$2$

$1000099913\mathrm{.}287712100001099950000132877\mathrm{.}12381$E$+08$

$2000099914\mathrm{.}2877122000020999100000285754\mathrm{.}24764$E$+08$

$4000099915\mathrm{.}2877124000040999200000611508\mathrm{.}49521\mathrm{.}6$E$+09$

$8000099916\mathrm{.}28771280000809994000001303016\mathrm{.}996\mathrm{.}4$E$+09$With the input size $N$ increasing, all these runtime functions grows.

With the input size $N$ increasing, some of these runtime functions grow at the same rate.

With the input size $N$ increasing, some of these runtime functions grow at the different rates.

With the input size $N$ increasing, runtime functions $T(N)=N,T(N)=N+999,$ and $T(N)=5**N$ grow at

the same scale.

With the input size $N$ increasing, the growth rate of $T(N)=999$ is constant.

Based on the scalability of growth rates of all these functions, we could use big $O$ notation to

categorize or classify these functions:

$T(N)=999=O(1),($The growth function is constant$)$

$T(N)=lo{g}_{2}N=O(logN),($The growth function is logarithmic$)$

$T(N)=N=O(N),($The growth function is linear$)$

$T(N)=N+999=O(N)$

$T(N)=5**N=O(N)$

$T(N)=5^{**}N+999=O(N)$

All these $N+999,N,5^{**}N,5^{**}N+999$ belong to the same group of growth functions which asymptotic

order is linear, according to input size $N.$

$T(N)=Nlo{g}_{2}N=O(NlogN),($The growth function is log$-$linear$)$

$T(N)=N^2=O(N^2),($The growth function is quadratic$)$

The asymptotic order of the growth functions: the group functions represented by $O(N^2)$ have

higher growth order than $O(NlogN),O(NlogN)$ is larger than $O(N),O(N)$ is larger than $O(logN),$ and

$O(logN)$ is larger than $O(1).$