CHOOSE2

Which of the given options provides the increasing order of complexity of functions f1, f2, f3 and f4:

f1(n) = 2^n

f2(n) = n^(3/2)

f3(n) = nLogn

f4(n) = n^(Logn)




•  f3, f2, f4, f1
•  f3, f2, f1, f4
•  f2, f3, f1, f4
•  f2, f3, f4, f1

Good solution:

1. n < nlog(n)
2. n^x < n^y if x < y
3. n^x < c^n where c is a constant (polynomials will eventually grow slower than exponentials)
4. log(n) < n
5. c^n < n! < n^n where c is a constant