Factorial

Input: n = 5
Output: 120
Explanation: 5! = 1 * 2 * 3 * 4 * 5 = 120

To compute the factorial, we have to iterate through every value from 1 to n and multiply that value to the product. How can we achieve this?

First of all, we should store this product somewhere as we compute it. That 'somewhere' is a variable, let's name it fact. For example, for n = 4:

var fact = 1   // fact is initially 1 = 1!
fact *= 2   // now fact is 1 * 2 = 2!
fact *= 3   // now fact is 1 * 2 * 3 = 3!
fact *= 4   // now fact is 1 * 2 * 3 * 4 = 4!

How can we extend this code to compute the factorial of any value of n?

With a loop! Let's use a for loop and a variable i to iterate through the numbers 1 to n:

var fact = 1   // fact is initially 1 = 1!
for (i <- 1 to n) {
	// what should we do here?
}

What should we do inside this loop?

Inside the loop, all we should do is multiply fact by i.
When the loop terminates, the answer lies in fact:

var fact = 1
for (i <- 1 to n) {
	fact *= i
}
return fact

We have a for loop that performs exactly n iterations, thus the Time Complexity is O(n).
The only extra space we use is the variable fact and the iterator variable i inside the loop, thus the Extra Space used is O(1).