Homework: Big-Oh for Recursive Functions

Question

This is a problem from my homework. I am not quite sure about how to solve a problem like this.

If T(n) = nT(n - 1) and T(1) = 3, then
a) T(n) = O(n^n)
b) T(n) = Ω(n!)
c) T(n) = O(2^(nlogn))
d) none of the above

I dont need exact answer to this problem (since its homework), but I would like to know the way to tell the bound of a recursive function.

Answer 1

Just try working through it. Suppose n = 3. How many iterations will there be? How about if n = 4? How fast does the number of iterations grow when you increase n?

Another way to look at it is: In the formula, how does a function "branch"? linear functions don't branch, they only have simple 1:1 recursion. Exponential functions will branch several times. Logarithmic functions branch, but reduce the complexity of the data they operate on... etc.

Answer 2

 For n = 4:

   T(4) = 4 * T(4-1)
     T(3) = 3 * T(3-1)
       T(2) = 2 * T(2-1)
         T(1) = 3

The execution time is 2 steps for every call ( the multiplication and the recursive call). For the given example, for 4 calls you will have 8 steps which are linearly executed (you don't have any combinatorial or logarithmic algorithm, so your function is bounded by O(n).

For the possible choices you have the answers would be:

a) T(4) = O(4^4) -> 256 

b) T(4) = Ω(4!) -> 24

c) T(4) = O(2^(4log4)) ~> 5.27

d) none of the above

So your choice should be d. Hopes it helps.