-1
$\begingroup$

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:

$T(n)=T(n-1)*n$

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:

$T(n+1)=T(n)*(n+1)=(n+1)!$

Using the assumption, I just replace $T(n)$ with $n!$ and get:

$T(n+1)=n!*(n+1)=(n+1)!$


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?

$\endgroup$
  • $\begingroup$ I think you're missing what the starting value $\;T(0)\;$ is: why do you assume it is zero? Is it given? Perhaps the recursive formula is only valid for $\;n\ge 2\;$ or something. I think this question's lacking information. $\endgroup$ – DonAntonio Oct 23 '16 at 11:45
  • $\begingroup$ It seems easier to write $T(n+1)=T(n)*(n+1)$ for your algorithm. $\endgroup$ – Dietrich Burde Oct 23 '16 at 11:48
  • $\begingroup$ @DonAntonio: I don't have to use $n=0$ as a base case, but even if I use, let's say, $n=100$, I always will come back to $T(0)$ which will always be $0$. $\endgroup$ – Arthur Oct 23 '16 at 11:48
  • $\begingroup$ @DonAntonio: There is no additional information to this assignment. It just says: Find a function $f$, such that $T(n)=T(n-1)*n\in\Theta(f)$ $\endgroup$ – Arthur Oct 23 '16 at 11:54
  • $\begingroup$ @Arthur So then you have also to come up with $\;T\;$ , not only with $\;f\;$ ? That looks weird... $\endgroup$ – DonAntonio Oct 23 '16 at 12:01
1
$\begingroup$

Observe that for a constant $\;k\in\Bbb R\;$ , we have that

$$T(n)=kn!=\Theta(n!)\iff\;\text{there exist constants}\;\;k_1,k_2\in\Bbb R\;\;s.t.\;\;$$

$$k_1\le\frac{T(n)}{n!}\le k_2$$

and the claim follows at once.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.