Arrange the following 9 functions based on the incremental nature

• Dec 17th 2012, 12:28 AM
SmartMonkey
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
• Dec 17th 2012, 05:47 AM
emakarov
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})$.
• Dec 17th 2012, 07:38 AM
SmartMonkey
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
• Dec 17th 2012, 07:45 AM
emakarov
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$.
• Dec 17th 2012, 07:47 AM
SmartMonkey
Re: Arrange the following 9 functions based on the incremental nature
That was so helpfull. you made everything much clearer.. sorry for my english