Question

Order the following functions by growth rate : N, N^1/2, N^1.5, N², NlogN, N(logN)², NlogN², 2/N, 2N, 2^N/2, 37, N³, and N²logN. Also, Indicate which functions grow at the same rate.

Please complete and explain step by step

Answer 1

To order these functions, let take N value as max as possible
let N=2^10
N: 2^10
N^(1/2) = (2^10)^(1/2) = 2^5
N^(1.5) = N^(3/2) = (2^10)^(3/2) = 2^15
N^2 = (2^10)^2 = 2^20
NlogN = (2^10)log(2^10)= (2^10)*10
N(logN)^2 = (2^10)(log(2^10))^2 = (2^10)*(10^2)
NlogN2 = (2^10)log(2^10)^2 = (2^10)log(2^20) = (2^10)*20
2/N = 2/(2^10)= 1/(2^9)
2^N = 2^(2^10) = 2^1024
2^(N/2) = 2^((2^10)/2) = 2^(2^9) = 2^512
37:37
N^3: (2^10)^3 = 2^30
(N^2)logN: ((2^10)^2)log2^10 = (2^20)*10
ordering from low to high:2/N,37,N^(1/2),N^(1.5),N,NlogN,NlogN^2,N(logN)^2,N^2,N^2logN,N^3,2^N/2,2^N
functions with same growth rate:
2^N, 2^N/2