The increasing order of following functions in terms of asymptotic complexity…

Step-by-Step Analysis

• Comparing f1(n) and f2(n):

  • f2(n) grows strictly linearly, so its complexity is O(n). The large constant coefficient (107) does not affect its asymptotic growth rate.

  • For f1(n), we have n0.999999 log n. A fundamental rule of asymptotic growth is that any polynomial term nepsilon (where epsilon > 0) grows faster than any polylogarithmic term log n.

  • Let's compare f1(n) and f2(n) by dividing them by n0.999999:

    $$\frac{f_2(n)}{n^{0.999999}} = \frac{10^7 n}{n^{0.999999}} = 10^7 n^{0.000001}$$

  • As n → ∞, n0.000001 will eventually grow larger than log n. Therefore, f2(n) grows faster than f1(n).

  • Order: f1(n) < f2(n)

• Comparing f2(n) and f4(n):

  • f2(n) = O(n) (Linear)

  • f4(n) = O(n2) (Quadratic)

  • A quadratic function always grows asymptotically faster than a linear function.

  • Order: f2(n) < f4(n)

• Comparing f4(n) and f3(n):

  • f4(n) = n2 (Polynomial)

  • f3(n) = 1.000001n (Exponential)

  • An exponential function an (where a > 1) will always outgrow any polynomial function nk as n approaches infinity, no matter how small the base a is or how large the exponent k is. It just takes a massive value of n to cross over.

  • Order: f4(n) < f3(n)

Final Asymptotic Order

Combining these insights, the correct increasing order of growth is:

f1 < f2 < f4 < f3