algorithm - 宿題: 再帰関数のビッグオー

Question

これは私の宿題の問題です。このような問題を解決する方法についてはよくわかりません。

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

この問題に対する正確な答えは必要ありませんが（宿題なので）、再帰関数の境界を伝える方法を知りたいです。

Answer 1

 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.