Exercise $4$: $($Empirical Analysis of Performance and Algorithm Visualization$)$

$[$CL$02\mathrm{.}1,$ S$1,1$ Mark$]$

a$)$ Take an available implementation of the Selection Sort algorithm. Run it on a randomly generated data of fixed size and note down the execution time. Repeat the experiment $10$ times on the same data and fill the table below.

$\backslash$table$[[$Trial #$,\backslash$table$[[$Execution Time$],[($ms$)]]],[1,],[2,],[3,],[4,],[5,],[6,],[7,],[8,],[9,],[10,]]$

b$)$ Why is the execution time different for each trial?

c$)$ A good way to approximate the execution time is to take the average time of multiple trials. Do this for different data sizes and fill the table below:

$\backslash$table$[[\backslash$table$[[$Data Size $($number of$],[$elements$)]],$Average Execution Time of $10$ trials $($ms$)],[10,],[100,],[1000,],[5000,],[10,000,],[50,000,],[100,000,],[500,000,],[1,000,000,]]$

d$)$ Plot the data in the table above. Average time along $y-$axis and the data size along $x-$axis.

e$)$ The time complexity of Selection Sort algorithm is $O(n^{{?}^{{?}^{?}}}2).$ Plot it and verify that the curve looks like the one in $($d$).$