Description

1. Answer the following questions on the big-oh notation.

(a) Explain what g(n) = O(f (n)) means. time: 5’ 

(b) Explain why the statement: “The running time of algorithm A is at least O(n2 )” is meaningless. time: 5’

(c) Given two functions f = Ω(log n) and g = O(n), consider the following statements. For each statement, write whether it is true or false. For each false statement, write two functions f and g that show a counter-example

(d) For each one of the following statements, write two functions f and g that satisfy the given condition.

2. Write the pseudo-code of a function called findLargest that finds the largest number in an array using a divide-and-conquer strategy. You may use a syntax similar to Java. Also, write the time complexity of your algorithm in terms of big-oh notation. Briefly justify your complexity analysis. time: 20’ int findLargest(int [] A) { 

3. Illustrate the execution of the merge-sort algorithm on the array

For each fundamental iteration or recursion of the algorithm, write the content of the array. Assume the algorithm performs an in-place sort.