Explain why the statement: “The running time of algorithm A is at least O(n2 )” is meaningless. time: 5’
computer science
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.
