Page 1. [25 points] Answer the following questions true or false: a) n log n= en) b) n? - 3n2= (n) n log n= On21) n! = ((21) e) n = n(n). f) 12n2 + 6n = o(n) If T(n) = o(g(n)) then T(n) = O(g(n)). h) A function f(n) can be both O(n) and 2(n). O(n log n) is the same as O(n) because, in all practical cases, log n is smaller than some constant. 1) 1+ 2+ 3+...+(n - 1) +n= On). k) The bisection method is an iterative algorithm that improves the accuracy of its approximation of the root of an equation f(x) = 0 by a factor of two in each iteration. It can be viewed as an example of a decrease-and-conquer algorithm where a smaller version of the same problem is solved in each step. 1) Given an unsorted array of n integers, the median element in the array can be found in O(n) time in the average-case. m) Merge sort is an in-place sorting algorithm. n Quicksort is a stable sorting algorithm. 0) Counting sort, a linear-time sorting algorithm that is often used as a subroutine by radix sort, is a stable sorting algorithm