2

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.

Mike
  • 47,263
  • 29
  • 113
  • 177
Allan Jiang
  • 11,063
  • 27
  • 104
  • 165

2 Answers2

6

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.

Amadan
  • 191,408
  • 23
  • 240
  • 301
  • I am not 100% sure about the first part you mentioned. take my question as an example. when `n = 3` I know there will be function calls like this `T(1) =>(return result to) 2T(2-1) => 3T(3-1)`, but how do I determine the bound from that? – Allan Jiang May 15 '12 at 09:54
  • So, you determined that there will be 3 iterations when `n = 3`. How about `n = 4`? Can you predict for `n = 5`? – Amadan May 15 '12 at 09:58
  • I think there are 4 iterations when `n = 4` and `n = 5` there are 5 iterations? but if its like this, wont it be `O(n)`? – Allan Jiang May 15 '12 at 10:03
  • Indeed it will, @AllanJiang, indeed it will. – Amadan May 15 '12 at 10:05
  • Thank you for your answer, but what if the problem is like `T(n) = T (n -1) + T(n - 2)`, just like a Fibonacci function? will this be `O(n^2)`? what are the cases when its `O(log^n)` or `O(nlog^n)` – Allan Jiang May 15 '12 at 10:10
  • Umm, vice-versa. `O(2^n)`, when computed naively. It's because for each additional `n`, you're calculating two whole calculations of `f`. You can see [this](http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence) question for more details. Also check out the [thread linked in the comments](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it). – Amadan May 15 '12 at 10:21
3
 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.

Angelos Kapsimanis
  • 991
  • 8
  • 12
  • Hi Thank you for your answer=) just ask a small further question, can you give me a recursive function which has `O(nlogn)` or `O(logn)`? Thank you – Allan Jiang May 15 '12 at 10:17
  • Sure, for O(nlogn) Fast Fourier Transform, heapsort, quicksort, merge sort or f(x) = n + log(n)! for O(logn) a binary search on a sorted array or any operation in a binomial heap and calculating Fibonacci sequence with matrix multiplication. Check wiki about them, they give excellent explanations of all algorithms. – Angelos Kapsimanis May 15 '12 at 10:42