This question is part math and part computer science. But since it is mainly about an induction proof, I guess I'll post it here.
I have a recursive algorithm where the time complexity is expressed with this formula:
I need to find the exact bound of the algorithm using big Theta notation $\Theta()$
It's fairly easy to see that $T(n)\in\Theta(n!)$
I use induction to prove it. It is the base case which troubles me, so let's skip it for now. Let's assume I have proven the formula for some number $n$.
So, assuming $T(n)=T(n-1)*n=n!$ I have to prove now:
Using the assumption, I just replace $T(n)$ with $n!$ and get:
Now, back to the base case. Let's use $n=0$.
I get $T(0)=T(0-1)*0=0=1=0!$, which is a contradiction.
Let's use $n=1$:
$T(1)=T(1-1)*1=T(0)*1=0*1=0=1=1!$, I think you can see my problem now.
No matter what number I use as the base case, I get $0=x$ with $x\neq 0$.
Even though I have proven the formula for $n+1$ I cannot prove it for a starting $n$.
Does that mean $T(n)\notin\Theta(n!)$ ?
Or is induction the incorrect way of proving this?