MULTIPLE CHOICE:

Question 1: Determine the order of grown of the runtime of a function that takes an array as input based on the following experimental data:

array size	time
1000	3.142
2000	12.559
3000	28.281
4000	50.269

	a) cubic
	b) constant
	c) quadratic
	d) linear

Question 2: What is the running time for the following function with respect to the size of the input array?

public int f(int[] array) { int mid = array.length / 2; int count = 0; for(int i = 0; i < mid; i++) { for(int j = mid; j < array.length; j++) { if (array[i] == array[j]) count++; } } for(int k = 0; k < array.length; k++) array[k] = -array[k]; return count; } 

	a) linear
	b) cubic
	c) quadratic
	d) linearithmic

Question 3: What is the running time for the following function with respect to the size of the input array?

public int f(int[] array) { int mid = array.length / 2; int count = 0; for(int i = 0; A.length; i++) { for(int j = i; j > 0; j /= 2) { array[i] += array[j] } } } 

	a) linearithmic
	b) logarithmic
	c) linear
	d) quadratic

Question 4: You have determined that the running time of a particular algorithm has cubic order of growth with respect to the size of the input. You have run the algorithm 3 separate times on an array of size 1,000 and found that the median running time was 21.7 seconds. Which of the expressions below is the best tilde approximation for the running time of the algorithm?

	a) ~0.0000000217 * n3
	b) ~0.0000217 * n3
	c) ~0.0217 * n3
	d) ~0.0000217 * n2