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$

Group of answer choices

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$)=$ log$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$)=$ N log$2$N $=$ O$($N logN$)($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$($N logN$),$ O$($N logN$)$ is larger than O$($N$),$ O$($N$)$ is larger than O$($logN$),$ and O$($logN$)$ is larger than O$(1).$