Exercise $2.$ We collected data on the running time of a program on inputs of various sizes and

got the following results:

Size of the input n $501002004008001600$

Time in seconds $0\mathrm{.}170\mathrm{.}742\mathrm{.}6911\mathrm{.}0244\mathrm{.}66178\mathrm{.}5$

$1.$ Explain why the runtime cannot be exponential: of the form T$($n$)$ c

n

for some constant

c $>1?$

$2.$ Suppose the runtime is polynomial: of the form T$($n$)$ cnk

for some constants c $>0$ and

k $>=1.$ Estimate k as well as possible.

$3.$ Based on this estimation,