ansaurus

Question

Recurrence Relation

Answer 1

+5 A:

I assume that you have bad information. The second recurrence relation you cite is the correct one, as you have observed. The first one just generates the natural numbers.

jprete 2009-09-04 15:27:21

Answer 2

+2 A:

Where did you find the first one ? It's completely wrong.

It's only going to add 1 each time whatever the value is .

LB 2009-09-04 15:27:59

Answer 3

+1 A:

This question is very confusing... You first formula is not factorial. It is simply T(n) = n + 1, for all n. Factorial of n is the product of the first n positive integers: factorial(1) = 1. factorial(n) = n * factorial(n-1). Your second formula is essentially correct.

Dima 2009-09-04 15:31:39

So what is the time complexity for the second algorithm??Is it exponential?

Prasoon Saurav 2009-09-04 15:54:04

Prasoon Saurav 2009-09-04 15:58:01

The theoretical time complexity is linear. To compute a factorial of n you need to perform n multiplications: O(n). The value of n!, on the other hand grows faster than any exponential. Of course, the complexity of computing n! increases if you want full precision for a large n, so that n! has more bits than the integer on your machine. Then you need to perform infinite precision arithmetic, which adds complexity.

Dima 2009-09-04 16:06:41

even with your pointer, i'm not able to find the right relation. Are you sure you were not looking at the Fibonacci number ? (it's closer but not right either..)

LB 2009-09-04 16:09:05

This is called "flat recursion", i. e. the function only makes one recursive call to itself. Flat recursion takes liner time to compute. On the other hand, if the function makes more than one call to itself, you have a deep recursion, that takes exponential time. Example: f(x) = f(x-1) + f(x-2). At each level of recursion you double the number of calls to f, i. e. f() is called 2^n times.

Dima 2009-09-04 16:10:59

>>The theoretical time complexity is linear.Can it be proven using the recurrence relation??

Prasoon Saurav 2009-09-04 16:12:24

Another point: please be careful not to confuse the bound on the time it takes to compute a function, and the bound on the value it returns. The bound on the time it takes to compute n! is O(n). The bound on the value of n! is O(n!) > O(k^n) for any k.

Dima 2009-09-04 16:13:24

@Prasoon Sure. To compute n! recursively you make n recursive calls.

Dima 2009-09-04 16:15:27

@Dima<br>If you try solving its recurrence relation will u get T(n)=O(n) ?The recurrence relation is T(n)=1 when n=0T(n)=n*T(n-1) when n=0How T(n)=O(n).??

Prasoon Saurav 2009-09-04 16:18:25

Ok, I see. What you are after is the bound on the value of T(n). In that case no, T(n) != O(n). T(n) = O(n!) > O(k^n) for any

Dima 2009-09-04 16:57:53

Answer 4

+5 A:

Looks like T(n) is the recurrence relation of the time complexity of the recursive factorial algorithm, assuming constant time multiplication. Perhaps you misread your source?

chrispy 2009-09-04 16:59:52

ansaurus

tags:

views:

answers:

Recurrence Relation

related questions