Question

Give the asymptotic complexity of each of the following functions in simplest terms and then order the functions by asymptotic dominance.

{eq}a) f_1(n)=log(n^3)+log(n^5) \

b) f_2(n)=2^{n^2}+10n^{0.5} \

c) f_3(n)=6n^{1.2}+3n^{0.8} \

d) f_4(n) = 3nlog(n^2+3)+n^4 \

e) f_5(n)=(log(n^2)+5n+4)^{0.2} \

f) f_6(n)=sqrt{3n^2+4n^5} \

g) f_7(n)=2^{64}

{/eq}

EXPERT ANSWER

Asymptotic complexity estimates the rate of growth of a function using the dominant terms. The complexity of an algorithm is often the running time of the algorithm translated into a program, but not always.