Description
(1. 10pts)
Compare the following pairs of functions in terms of order of magnitude. In each case, say
whether f(n) = O(g(n)), f(n) = Θ(g(n)), and/or f(n) = Ω(g(n))
f(n) g(n)
a. 100n + logn n + (logn)
2
b. logn log(n
2
)
c. n
2
logn n(logn)
2
d. n
1
2 (logn)
5
e. n2
n 3
n
(2. 10pts)
Algorithm Mystery(A: Array [i..j] of integer)
i & j are array starting and ending indexes
begin
if i=j then return A[i]
else
k=i+floor((j-i)/2)
temp1= Mystery(A[i..k])
temp2= Mystery(A[(k+1)..j]
if temp1