Search for question
Question

Numéro 1. (34 pts) COMPLEXITY

(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