The question prompt is as follows:
Consider the function $f(n)$ defined as: $$f(n) = \begin{cases}n(n-1)f(n-2) & n > 1\\1 & n=0,\; n=1\end{cases}$$
How may be $g(n)$ be defined to make $f(n) \in \mathcal O(g(n))$? (I'm supposed to choose one response from $1$ and a response from $2$)
- For $n>0$, define $g(n)$ as:
Option 1: $g(n) = g(n-1) + n$
Option 2: $g(n) = ng(n-1)$.- Then, assign:
Option 1: $g(0) = 0$
Option 2: $g(0) = 100$.
Now, I solved the recursive equation and got the following: $$f(n) = n!$$
If we define $g(n) = g(n-1) + n$: $$g(n) = n(n+1)/2 + \{0\text{ or }100\}$$ If we define $g(n) = n\cdot g(n-1)$: $$g(n) = n! \cdot \{0\text{ or }100\}$$
(The $\{0\text{ or }100\}$ because when $g(0)$ could be $0$ or $100$.)
However, I am not seeing how either definition of $g(n)$ yields $\lim_{n\to\infty} (f(n)/g(n)) = 0$.
Your problem is that you're seeking the wrong thing limit. In order for $f(n)$ to be $\mathcal O(g(n))$, you want: $$\lim_{n\to\infty} \frac{f(n)}{g(n)} = c, \quad 0\leq c < \infty$$
Clearly, if we choose $g(n) = n!\cdot g(0)$ and $g(0) = 100$, the resulting value is $c=\frac{1}{100}$.
You probably were confused with the definition of little-oh: $$f(n)\in o(g(n))\iff \lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$$
To conclude: you did everything else right, except you messed up the limit definition of $\mathcal O(\cdot)$.