1. Order the following 14 functions by increasing growth rate (using O notation and the features of big O). Please indicate out specifically there any two functions grow at the same rate. (Hint: You can use insertion sort, using the formula on slides 48 to compare any two functions)
N, sqrt(N), N1.5, N2, N log N, N log log N, N log2 N, N log(N2), 2/N, 2N, 2N/2, 37, N3, N2 log N
2. Suppose T1(N) = O(f(N)) and T2(N)=O(f(N)). Is it True/False for the following statement? Give reasons. (hint: check by the definition of big O)
a. T1(N) + T2(N) = O(f(N))
b. T1(N) - T2(N) = o(f(N)
c. T1(N)/T2(N) = O(1)
d. T1(N) = O(T2(N))
3. A very famous algorithm for computing the greatest common divisor is called Euclid algorithm, using a search engine to find this algorithm and
a. Submit the program it in source code you found from internet
b. show the running results by inputting a few numbers
c. Analysis it and what is the order of the running time of Euclid algorithm?
4. For every pass (the moment for the outer loop in the program), show the result of the whole array when the original sequence is {3, 1, 4, 1, 5, 9, 2, 6, 5} if it is using
a. Bubble sort
b. Insertion sort
c. Selection sort
(hint: you could use the program to run the above sequence and then display the result of each pass)