Question 1:

Given the functions that you graphed in the previous question, seen below in a lettered list. Put them in order from slowest growing to most rapid growth.

x2

f(x)=1

xlog(x)

2x

log(x)

x3

x

Question 2:

Assuming that an algorithm was found to have runtime proportional to f(n)=4n23n+7, which of the following are true? May be more than one.

None of these.

f(n) = O(n^2)

f(n) = O(n)

f(n) = O(n^3)

Question 3:

Given an array of numbers sorted from lowest to highest, what would the (closest) runtime be for the best algorithm to find the largest number in the array?

O(1)

O(n^2)

O(n)

None of these

Question 4:

What is the best (closest) asymptotic bound for this algorithm?

for (i = 0; i < n; i++)

for (j = 0; j < n; j++)

a[i][j] += b[i][j] + c[i][j];

Constant time

None of these

O(n)

O(n^2)

O(1)

Linear Time

O(i) + O(j)