Asymptotic notations

Question

The increasing order of following functions in terms of asymptotic complexity is:

$\large \\ f_1(n)= n^{0.999999} \log n \qquad // \log n \text{ is not power of } n\\ f_2(n)=10000000*n \\ f_3(n)=10000000^n\\ f_4(n)=n^2$

(a) f1(n);      f4(n);      f2(n);      f3(n) 
(b) f1(n);      f2(n);      f3(n);      f4(n) 
(c) f2(n);      f1(n);      f4(n);      f3(n) 
(d) f1(n);      f2(n);      f4(n);      f3(n)

Answer 1

Incorrect Solution:

critical problem in this question is to find out which is greater between $f_1$ and $f_2$, for that purpose we take $\log$ on both functions:

for $f_1$:
$$\log \log n + 0.999999 \log n$$

for $f_2$:
$$\log n + \log 10^7$$

in $f_1$ we are adding a non-constant entity but that's not the case with $f_2$. Hence, $f_1$ is greater.

we get answer = option C like this.  BUT this is FALSE. Even after taking $\log$ we cannot deduce a meaningful conclusion coz Product terms cannot be ignored, See discussion in comments below.

So, a more robust approach is to see mathematically what happens when $n \rightarrow \infty$

---

Correct Solution:

let us assume that 0.999999 = 0.5, just to make things simple, it is a constant & also a fraction so it will continue to maintain its nature during this process, so this move is ok. Now, we have:
$\begin{align*} \lim_{n \rightarrow \infty} \left| \frac{f_1(n)}{f_2(n)} \right| &= \lim_{n \rightarrow \infty} \frac{\sqrt{n} \log n}{n}\\ &= \lim_{n \rightarrow \infty} \frac{\frac{1}{\sqrt{n}} + \frac{\log n}{2 \sqrt n}}{1}\\ &= \lim_{n \rightarrow \infty} \frac{2+ \log n}{2\sqrt{n}}\\ &= \lim_{n \rightarrow \infty} \frac{0+\frac{1}{n}}{2\times \frac{1}{2\sqrt{n}}}\\ &= \lim_{n \rightarrow \infty} \frac{1}{\sqrt{n}}\\ &= 0 \end{align*}$

since, at $n \rightarrow \infty$ shows that the value of the expression = $0$ this means that for sufficiently large $n$ the denominator has to be a much bigger value that is making the expression $=0$. So, $f_2$ is asymptotically bigger.

Hence, answer = option D

Comments

umm.. no. $f_1$ is not $O(n^{0.\rm whatever})$, because it has a multiplicative factor of $\log n$. This is analogous to the fact that $n\log n \notin O(n)$.

$f_2$ still grows faster than $f_1$ though.

Here's how you can think of it:

• $n^c$ always grows faster than $\log^k n$. (we're talking about positive values of $n, c, k$ here)
   
• $n^1 = n^{0.99} \times n^{0.01}$. Comparing it with $n^{0.99} \times \log n$, we see that $\log n < n^{0.01}$, and hence $n^{0.99}\log n < n^{0.99}\cdot n^{0.01} = n$

---

Taking $\log$ doesn't exactly fail. You just need to be careful with it.

Normally, constant multiplicative factors are ignored in asymptoticlly comparing two functions. But when you compare the $\log$ values of those functions, any constant multiplicative factors become constant additive factors.

So, if you need to compare $f(n), g(n)$, but you're comparing $\log f(n), \log g(n)$, you canNOT ignore constant multiplicative factors. You can only ignore constant additive factors.

For example,

Case in which multiplication changes to addition:

$f(n) = n, g(n) = 2n$. Since constant multiplicative factors can be ignored, we get $f(n) = \Theta(g(n))$.
Similarly, $\log(f(n)) = \log n, \log(g(n)) = \log n + \log 2$. Since we took a $\log$, we can only ignore constant additive factors. So, we ignore the $+ \log 2$, and get $f(n) = \Theta(g(n))$

Case in which exponentiation changes to multiplication.

$p(n) = 2^n, q(n) = 3^n$. Since there are no constant multiplicative factors to ignore here, and constant exponential factors $(2, 3)$ cannot be ignored, we get that $2^n < 3^n$.

Now, $\log(p(n)) = 2 \log n, \log(q(n)) = 3 \log n$. Since we took a $\log$, we canNOT ignore the constant multiplicative factors! If we did ignore them, we would conclude that $2^n = \Theta(3^n)$, which would be wrong! The correct result is, $2^n < 3^n$.

Note: $<$ means grows slower than.

---

ok

Conclusion:

• It was the split of $1$ into two fractional powers, that did the job.
• We cannot ignore product terms after taking $\log$. See, comparison of $n^2$ and $n^3$ after taking $\log$.

Answer 2

https://gateoverflow.in/27980/asymptotic-notations