(A)Arrange the following list of functions in increasing order of growth rate. That is, if function...

Transcribed Image Text:

(A)Arrange the following list of functions in increasing order of growth rate. That is, if function g(n) follows function f(n), then it should be the case that f(n) is O(g(n)) (the base of logarithms is 2). Justify in simple words. (You do not have to show detailed calculations.) fi(n) = 17n + (/2) f2(n)= 7n log log n f3(n) = 20n log n +5n f4(n) = 4n + 3 log(n) f5(n) = 2n fe(n)=2(3logn) Let ai (b) 8 and an an-1 + 2an-2, where n 3. Use induction to prove that an = 3 2n-1 + 2(-1)" for all n E N. Note: you will need to use strong induction (sometimes known as complete induction) to solve this problem. = 1, 0: = = (A)Arrange the following list of functions in increasing order of growth rate. That is, if function g(n) follows function f(n), then it should be the case that f(n) is O(g(n)) (the base of logarithms is 2). Justify in simple words. (You do not have to show detailed calculations.) fi(n) = 17n + (/2) f2(n)= 7n log log n f3(n) = 20n log n +5n f4(n) = 4n + 3 log(n) f5(n) = 2n fe(n)=2(3logn) Let ai (b) 8 and an an-1 + 2an-2, where n 3. Use induction to prove that an = 3 2n-1 + 2(-1)" for all n E N. Note: you will need to use strong induction (sometimes known as complete induction) to solve this problem. = 1, 0: = =