Determine if this statement about Big O notation is true or not.

Question

$f(n) = n^2 + n^{0.5}$

$g(n) = [g(n-1)]^2 + [g(n-2)]^2$ for $n \geq 3$, where $g(1) = 1$ and $g(2) = 2$

The statement: $2^{2^{f(n)} }= Ω(g(n))$

The $\lim_{n \rightarrow \infty} \frac{2^{2^{f(n)} }}{g(n)}$ can't be computed easily since $g(n)$ has a recurrence relation.

How do I approach it?

Answer 1

I took a numerical approach to this particular problem. I calculated the first $11$ terms for $g(n)$, i.e., $g(1)$ through $g(11)$. The table below shows the results.

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & \log_{2}\left(g(n)\right) \\ \hline 1 & 0.0\\ \hline 2 & 1.0\\\hline 3 & 2.321928094887362\\\hline 4 & 4.906890595608519\\\hline 5 & 9.813781191217037\\\hline 6 & 19.609640474436812\\\hline 7 & 39.12617154448214\\\hline 8 & 78.40434618240933\\\hline 9 & 157.13062045970602\\\hline 10 & 314.26124091941205\\\hline 11 & 628.8444099337115\\\hline \end{array}$$

Notice that the second column presents the $\log_{2}$ of $g(n)$, which grows so fast and so huge that my computer is not able to compute it for $n > 11$ (at least not with Python and Matlab; $g(11)$ has $190$ digits and the number of digits double for every iteration).

The right column of the table can be approximated to $$\log_{2}\left(g(n)\right) = 0.3051\exp\left(0.6937n\right)$$ with Matlab's curve fitting tool. The image below shows that the fit is pretty good.

General model Exp1:
 f(x) = a*exp(b*x)
Coefficients (with 95% confidence bounds):
   a =      0.3051  (0.3017, 0.3086)
   b =      0.6937  (0.6927, 0.6948)

Goodness of fit:
  SSE: 0.46
  R-square: 1
  Adjusted R-square: 1
  RMSE: 0.2261

Therefore, $$g(n)\simeq2^{0.3051\exp\left(0.6937n\right)}$$

From WolframAlpha, $$\lim_{n\to\infty} \dfrac{2^{2^{n^2 + n^{0.5}}}}{2^{0.3051\exp\left(0.6937n\right)}} \to \infty$$

With a slightly different fit to the curve,

General model Power2:
 f(x) = a*x^b+c
Coefficients (with 95% confidence bounds):
   a =   2.944e-05  (4.097e-06, 5.479e-05)
   b =       7.032  (6.671, 7.393)
   c =       5.808  (0.2546, 11.36)

Goodness of fit:
  SSE: 284.2
  R-square: 0.9993
  Adjusted R-square: 0.9991
  RMSE: 5.96

you can show that

$$\lim_{n\to\infty} \dfrac{2^{2^{n^2 + n^{0.5}}}}{2^{2.944\mathrm{e}{-}05 n^{7.032} + 5.808}} = \infty$$

And so, $f(n)\in\Omega\left(g(n)\right)$.

Answer 2

First prove $g(n) \le 2^{2^{n-1}-1}$ by induction on $n$ as follows. It is true for the base cases (equality holds). It is clear that $g$ is increasing, so $g(n) = g(n-1)^2 + g(n-2)^2 \le 2g(n-1)^2 \le 2\cdot (2^{2^{n-2}-1})^2 = 2^{2^{n-1} - 1}$, as required.

Once we have this fact, your limit is easy to compute (or at least bound in the way we need), as $\frac{2^{2^{f(n)}}}{g(n)} \ge 2^{2^{f(n)} - 2^{n-1} + 1} \ge 2^{2^{n^2} - 2^{n-1} + 1} \to \infty$, as needed.

Answer 3

For $n\ge 3$ we have $0<g(n-2)^2<g(n-1)^2$ so $0<g(n-1)^2<g(n)<2g(n)^2,$ so $$2\log g(n-1)<\log g(n)<\log 2+2\log g(n-1),$$ so $$2^{n-2}\log g(2)<\log g(n)<(n-2)\log 2+2^{n-2}\log g(2)$$ by induction on $n\ge 3,$ and $g(2)=2 $ so $$2^{2^{n-2}}<g(n)<2^{n-2+2^{n-2}}.$$

Answer 4

The $g_n$ are given in sequence $A000283$ in $OEIS$ (have look here). I you look at the formula, in year 2003, Benoit Cloitre proposed $$g_n=\left\lfloor A^{2^{n}}\right\rfloor$$ where $$A=1.23539273778543688962233101322844082434745718691367945473360\cdots$$ is "almost" $[\log(5) ]^{e^\gamma}-\log(3)=1.235392625$

Now it is quite obvious from the formulae that $$r_n=\frac{2^{2^{f(n)} }}{g(n)}\to \infty$$

Considering $\log [\log (r_n)]$ and computing a few values before overflows $$\left( \begin{array}{cc} n & \log [\log (r_n)] \\ 1 & 1.01978 \\ 2 & 3.36260 \\ 3 & 7.07101 \\ 4 & 12.1101 \\ 5 & 18.5121 \\ 6 & 26.2846 \\ 7 & 35.4316 \\ 8 & 45.9554 \\ \end{array} \right)$$

If you plot these last results, you will see that they perfectly align along a quadratic in $n$.