(a) (3 points) True or false?
(i) 2n+1 = O(2)
Response :
(ii) 2³ € (2)
Response :
(iii) 2log, n! € (n log, n)
Response :
(b) (3 points) For each of the following pairs of functions f(n) and g(n), say if f(n) = O(g(n)),
f(n) = (g(n)) or f(n) = (g(n))
(i) f(n)=√n, g(n) = log n²
Response:
(ii) f(n) = log²n, g(n) = log n
Response:
(iii) f(n) = 5, g(n) = log 5
Response:
(c) (3 points) For each of the following pairs of functions f(n) and g(n), say if f(n) = O(g(n)),
g(n) € O(f(n)) or both
(i) f(n) = (n²-n), g(n) = 6n
Response:
(ii) f(n) = nlogn, g(n) = n√n/3
Response :
(iii) f(n) = n¹87, g(n) = 8log, n
Response :
(d) (3 points) For each of the following pairs of functions f(n) and g(n), if possible, find a
constant c> 0 such that f(n) ≤ cg(n) \n > 1.
(i) f(n) = n²+n+1, g(n) = 2n³
Response:
(ii) f(n) = n√n+n², g(n) = n²
Response:
(iii) f(n) = n√n, g(n) = logn +log, n-1
Response :
(e) (4 points) Give two functions f(n) and g(n) that satisfy the following properties. They may
not exist.
(i) f(n) = o(g(n)) and f(n) = (g(n))
Response :
(ii) f(n) (g(n)) and f(n) # N(g(n))
Response:
(iii) f(n) & (g(n)) and f(n) € w(g(n))
Response:
(iv) f(n) = f(g(n)) and f(n) = w(g(n))
Response :
(f) (6 points)
Partial information is available on the time complexity of five algorithms. These algorithms
do not necessarily solve the same problem. What more can you deduce? Be as precise as
Page 2/n
Fig: 1
Fig: 2