Master Theorem

Today I learned Master Theorem. However, there are not many explanations on the course slides. I was still confused after I read the course notes because it doesn't mention what "d" is in the definition. So I found the clearer (for me, and hope helpful for others too ) version of Master Theorem here:

For the definition of T we have, we can easily use Master Theorem to find the bounds of T without unwinding.

In summary, when we have a definition of T and want to use Master Theorem, we do the following steps:

1. calculate n^log_ba

2. compare if f(n) either greater, less than or equal to n^log_ba
        if f(n) = n^log_ba , then T(n) = θ ( n^log_ba lg n)
        if f(n) < n^log_ba , then T(n) = θ ( n^log_ba)
        if f(n) > n^log_ba , then T(n) = θ ( f(n) )

The summary above just for general case, and understanding. For preciseness, please refer to the Theorem 4.1. =]