retagged by
7,022 views
2 votes
2 votes

For each group of functions, sort the functions in increasing order of asymptotic (big-O) complexity:

$\begin{align*} &(a) \;\;f1(n) = n^{0.999999} * \log n \\ &(b) \;\;f2(n) = 10000000n \\ &(c) \;\;f3(n) = 1.000001^n \\ &(d) \;\;f4(n) = n^2 \end{align*}$

DOUBT- the solution shows that 1.000001^n has the highest time complexity since its an exponential function, but since the power is to 1.000001, it is growing very slowly, since base is tending to 1 only. Someone please check this.

retagged by

3 Answers

Best answer
5 votes
5 votes
$\begin{align*}

&f1(n) = n^{0.999999} * \log n \approx n * \log n\\
&f4(n) = n^2 \\
&f3(n) = 1.000001^n \\
\\
&\text{we will show that } f_3 \gg f_4 \gg f_1 \\ \\

\hline \\
&1.\quad n^a \gg n\log n \qquad \text{where a > 1 and } n \rightarrow \infty \\ \\
&\lim_{n\rightarrow \infty}\left [ \frac{n\log n}{n^a} \right ] \qquad a > 1 \\
&=\lim_{n\rightarrow \infty}\left [ \frac{\log n}{n^{a-1}} \right ] \\
&=\lim_{n\rightarrow \infty}\left [ \frac{\frac{1}{n}}{(a-1)n^{a-2}} \right ] \\
&=0 \\
&\Rightarrow \text{This proves }f_4 \gg f_1 \qquad \text{for a = 2}\\
\\
\\
&\text{Now}, \\
&2. \qquad b^n \gg n^a \qquad \text{where a,b > 1 and } n \rightarrow \infty \\
\\
&\Rightarrow  \lim_{n\rightarrow \infty}\left [ \frac{n^{k}}{b^n} \right ] \text{we will check this for k = 1} \\
\\
&\lim_{n\rightarrow \infty}\left [ \frac{n^{1}}{b^n} \right ] \\
&=\lim_{n\rightarrow \infty}\left [ \frac{n^{1}}{e^{n \ln b}} \right ] \\
&=\lim_{n\rightarrow \infty}\left [ \frac{1}{e^{n \ln b}.\ln b} \right ] \\
&=0 \qquad \left ( b > 1 \right )\\
\\
&\text{ Now, we will assume that for  } k = a > 1 \;\; \lim_{n\rightarrow \infty}\left [ \frac{n^{k}}{b^n} \right ] = 0 \;\; \text{ holds}
\\
&\lim_{n\rightarrow \infty}\left [ \frac{n^{a+1}}{b^n} \right ] \\
&=\lim_{n\rightarrow \infty}\left [ \frac{n^{a+1}}{e^{n \ln b}} \right ] \\
&=\lim_{n\rightarrow \infty}\left [ \frac{(a+1).n^{a}}{e^{n \ln b}.\ln b} \right ] \\
&=\lim_{n\rightarrow \infty}\left [ \frac{(a+1).{\color{red}{n^a}}}{{\color{red}{b^n}}.\ln b} \right ] \\
&=\lim_{n\rightarrow \infty}\left [ {\color{red}{0}}.\frac{(a+1)}{\ln b} \right ] \\
&=0 \\ \\
&\text{Thus, the induction proves  } \;\; b^n \gg n^a \qquad \text{where a,b > 1 and } n \rightarrow \infty \\
&\Rightarrow f_3 \gg f_4 \qquad \text{for large } \;\; n
\end{align*}$
selected by
1 votes
1 votes

n < nlog(n) < $n^{c}$ < $c^{n}$   

This is the increasing order of complexity.

For, $n^{0.999999}$ take its upper bound as $n^{1}$

$1.000001^{n}$ is an increasing function so it will be greater than $n^{2}$

Hence $f_{2}(n) < f_{1}(n) < f_{4}(n) < f_{3}(n)$

Related questions

0 votes
0 votes
1 answer
1
sushmita asked Sep 28, 2018
846 views
Find the complexity of the following code fragment:int i = 1; for(; i <= n logn; i++) { for(i++; i <= n; i++) { printf("1") } }
1 votes
1 votes
2 answers
2
sushmita asked Sep 28, 2018
704 views
Find the complexity of the following function when called with some integer n:void foo(n) { int i,j,k,x=0; for (i=1 ; i <= n ; i++) for (j=1 ; j <= i * i ; j++) for ( k ...
0 votes
0 votes
2 answers
3
sushmita asked Sep 28, 2018
791 views
FIND THE TIME COMPLEXITYint i=1,j; for(;i <= n;i + +) { for(j = i; j <= nlogn; j∗= 2) { sum++; } }
1 votes
1 votes
1 answer
4
Shubhanshu asked May 9, 2017
621 views
How the worst case of merge sort is O(n^2) according to the given MIT assignment pdf:-explain ?