Arrange the following 9 functions based on the incremental nature

Hello everyone..this is a part of an exercise on Algorithms and Complexity.

Arrange the following 9 functions based on the incremental nature(for example x^2 + 3x + 4. we will only use the x^2), if the

function f (n) is immediately before the function g (n) in order, should apply f (n) =

O (g (n)).

And here is the functions...

f1 = 2n+ n√n

f2 = 3^(log2n) 2 is the base but i don't know how to write it smaller.

f3 = 4^n

f4 = 4logn

f5 = (log(n!))^2

f6 = n^(2/3)

[logn]

f7 = Σi

i=1

f8 = (n^2)(3^n)

f9 = (5/6)^n

my thought is that f4 f5 and f7 are logarithm functions which are increasing slower than the other.

from these 3 f7 seems slower,after f4 and after this f5

f1 f6 are polynomial(faster than logarithm slower than exponential) and from them, f6 is the slower

so till now it should be like this f7 f4 f5 f6 f1

f3 f8 and f9 are exponential so they increase faster than the other.

About f9 (5/6)<1 so i am trying to find where it fits.. f8 is slower than f3

so till now it should be like f7 f4 f5 f6 f1 f8 f3

I am not sure where is the place for f9 and f2. and what it is exactly...logarithm or polynomial :S

Re: Arrange the following 9 functions based on the incremental nature

Not all exponential functions increase faster than polynomial. In this case, f9 is the only function out of nine that tends to zero rather than infinity.

Second, not every function that starts with log grows like a logarithm. We have $\displaystyle \log n!=\log(1\cdot\ldots\cdot n)=\log1+\dots+\log n\le n\log n$. This is the upper bound. For the lower bound we can use Stigling's approximation $\displaystyle n!\ge\sqrt{2\pi}\ n^{n+1/2}e^{-n}$, from where $\displaystyle \log n!\ge (n+1/2)\log n-n\log e+C$ for some $\displaystyle C$, and this is $\displaystyle \ge (1/2)n\log n$ from some point. So, $\displaystyle \log n!=O(n\log n)$ and $\displaystyle n\log n\le \log n!$, i.e., $\displaystyle \log n!=\Theta(n\log n)$. In particular, $\displaystyle \log n!$ grows faster than $\displaystyle n^{2/3}$.

Since $\displaystyle 3=2^{\log_23}$, we have $\displaystyle f_2(n) = 3^{\log_2n}=\left(2^{\log_23}\right)^{\log_2n} = 2^{\log_23\cdot\log_2n} = \left(2^{\log_2n}\right)^{\log_23} = n^{\log_23}$ and $\displaystyle \log_23=\ln 3/\ln 2\approx1.58$. So, $\displaystyle f_2(n)$ grows faster than $\displaystyle f_1(n)=O(n^{1.5})$.

Re: Arrange the following 9 functions based on the incremental nature

That was really helpfull. Just to be sure this is the answear right? 9 7 4 6 5 1 2 8 3

Re: Arrange the following 9 functions based on the incremental nature

Concerning f7, $\displaystyle \sum_i^ni=O(n^2)$, so $\displaystyle f_7(n)=O((\log n)^2)$, which grows faster than $\displaystyle f_4(n)=4\log n$.

Re: Arrange the following 9 functions based on the incremental nature

That was so helpfull. you made everything much clearer.. sorry for my english