Questions is from algorithams analysis and design course.

1. (a) Suppose a sorting algorithm takes 2 seconds to sort 50 items. How much time in seconds will the same algorithm take to sort 250 items if the number of operations the algorithm performs is exactly n2.

(b) Suppose algorithm A takes 500nlog2 n time and algorithm B takes 4n2 time. What is the smallest value of n (assuming n > 2) for which A will be faster than B? It may be dicult to do an exact calculation here; if so, try to give an approximate answer.

(c) For each of the following, indicate whether the statement is true or false:

i. 3n2 + 6n is O(n3).

ii. 3n4 is O(n2).

iii. n2 is O(log2 n).

iv. 200n2 is O(2n).

v. 3n2 + 9n is O(n2).

(d) If p(n) and q(n) are two functions such that p(n) is O(q(n)), does this always mean that for every value of n, p(n) q(n)? If you think the answer is yes, give a justication. If you think the answer is no, give a counterexample i.e. nd two functions p(n) and q(n) and a number y such that p(n) is O(q(n)) and p(y) > q(y).

2. (a) Trace insertion sort on the list 7,5,1,4,2,6 i.e. show what the list looks like after each iteration of the outer loop. Also, calculate the exact number of total data comparisons made. Note that a data comparison is when two dierent pieces of data are compared, and not when loop variables etc are compared.

(b) Trace the merge algorithm (not the complete merge sort) on the two lists 1,5,7,14 and 2,4,8,11. Show what the combined list (i.e. the merged list) looks like after every step and also calculate the exact number of total data comparisons made.