Problem $1.(25$ points$)$

For each of the following functions, indicate how much the function$$s value will change if its

argument is increased fourfold.

a$)$ b$)$ n c$)$ n

$2$ d$)$ n

$3$ e$)2$

n

Problem $2.(25$ points$)$

List the following functions according to their order of growth from the lowest to the highest:

$($n$2)!,5$log$($n$+100)$

$10$

$,2$

$2$n

$,0\mathrm{.}001$n

$4+3$n

$3+1,$ ln

$2$ n$,$

$3$

$,3$

n

$.$

Problem $3.(25$ points$)$

Consider the following algorithm.

ALGORITHM NoName$($A$[0..$n $1])$

$//$Input: An array A$[0..$n $1]$ of n real numbers

minval $$ A$[0]$; maxval $$ A$[0]$

for i $1$ to n $1$ do

if A$[$i$]<$ minval

minval $$ A$[$i$]$

if A$[$i$]>$ maxval

maxval $$ A$[$i$]$

return maxval $$ minval

a$)$ What does this algorithm compute?

b$)$ What is its basic operation?

c$)$ How many times is the basic operation executed?

d$)$ What is the efficiency class of this algorithm?

$2$

Problem $4.(25$ points$)$

Consider the following recursive algorithm for computing the sum of the first n cubes:

S$($n$)=13+23+...+$ n$3$