StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q18E

Expert-verifiedFound in: Page 370

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**Prove that Algorithm 1 for computing n! when n is a nonnegative integer is correct.**

The required algorithm is proved by induction.

**The algorithm is for when n is non-negative, the base case is .**

** factorial (0) = 0!**

** = 1**

By induction hypothesis,

$\begin{array}{r}\mathrm{factorial}\left(\mathrm{k}\right)=\mathrm{k}!\\ \text{factorial}(\mathrm{k}+1)=(\mathrm{k}+1)\cdot \text{factorial}\left(\mathrm{k}\right)\\ =(\mathrm{k}+1)\cdot \mathrm{k}!\\ =(\mathrm{k}+1)!\end{array}$

Therefore, the required algorithm is proved by induction.

94% of StudySmarter users get better grades.

Sign up for free