Rank the functions in increasing order of growth

Rank the functions in increasing order of growth:

F1(n) = n^(n/2)
F2(n) = (n/2)^n
F3(n) = (log n)^(log n)
F4(n) = 8^(log n)
F5(n) = n^(4/3)
F6(n) = n^3 - n^2
F7(n) = 2^(log n)^2
F8(n) = n log n

I have the functions ranked as follows: F8 < F5 < F6 ~ F4 < F3 < F7 < F1 ~ F2

f(n) < g(n) means f(n) = Little-o(g(n)) and
f(n) ~ g(n) means f(n) = Big-Theta(g(n))

Appreciate any second opinions on this! Particularly, F1 and F2 as well as F6 and F4.

Main intuition that I used was linear < polynomial < exponential and simplifying certain functions such as F4(n) = 8^(log n) = n^3 and F7(n) = 2^(log n)^2 = n^(log n).

1 Answer

Ranking of the functions should be: F3(n) < F7(n) < F4(n) < F8(n) < F5(n) < F6(n) < F1(n) < F2(n)

• F3(n) - Logarithmic functions grow slower than polynomial functions, and in general, exponential functions with larger bases grow faster than those with smaller bases.
• F4(n) will grow faster than F7(n), while they will both grow at an exponential rate, the base of the function will determine the rate of growth. Also, you can write 8^(log(n)) as 2^(3log(n)). Even though F4(n) is faster than F7(n), it is still slower than the polynomial function.
• F8(n) grows faster than logarithmic function but is smaller than polynomial function like n^2, n^3, n^4, ...
• F5(n) grows faster than F8(n) but is slower than the polynomial function like n^2, n^3, n^4, ...
• F6(n) is a polynomial function of degree 3 and is faster than the F5(n), but is slower than the exponential function F1(n).
• F2(n) > F1(n) - If you take the logarithm of both sides you get log((n/2)^n)=n(log(n) - log(2)) > log(n^(n/2))=(n/2)log(n).