Master Theorem & Recurrences

Question

I want to find out how to solve the Master Theorem for this code:

unsigned long fac (unsigned long n ) {
    if (n == 1 )
        return 1;
    else
        return fact(n-1)*n;
}

So based on the fact that I have only 1 time calling itself a=1. Besides that function call there is nothing else so O(n) = 1 as well. Now I am struggling with my b. Normally the general formula is:

T(n) = a*T(n/2) + f(n)

In this case I don't divide the main problem though. The new problem has to solve just n-1. What is b now? Because my recurrence would be:

T(n) = 1*T(n-1) + O(1)

How can I use the Master Theorem now, since I don't know my exact b?

Answer 1

The Master Theorem doesn't apply to this particular recurrence relation, but that's okay - it's not supposed to apply everywhere. You most commonly see the Master Theorem show up in divide-and-conquer style recurrences where you split the input apart into blocks that are a constant fraction of the original size of the input, and in this particular case that's not what's happening.

To solve this recurrence, you'll need to use another method like the iteration method or looking at the shape of the recursion tree in a different way.