using dynamic programming helps to reduce the time complexity of my recursive algorithm. how this actually happens? Is it possible to find factorial in less time with dynamic programming? (the largest value of the output is 10^14) asked 22 Dec '16, 16:34

If you just seek to speed up your recursive algorithm, memoisation might be enough. This is the technique of storing results of function calls so that future calls with the same parameters can just reuse the result. This is applicable if (and only if) your function does not have side effects and does only depend on its parameters (i.e. not on some state). It will save you time if (and only if) the function is called with the same parameters over and over again. Popular examples include the recursive definition of the Fibonacci numbers, that is f(0)=0 f(1)=1 f(n+2)=f(n+1)+f(n), n≥0 When evaluated naively, ff is called exponentially often. With memoisation, f(n)f(n) has always been computed by f(n+1)f(n+1) already, thus only a linear number of calls remains. answered 22 Dec '16, 17:20

@neget I don't think you will be able to store the factorial of number like $10$^$14$ since even Python can't also store/calculate it! Btw you can also look here : http://stackoverflow.com/questions/26989075/approachingdynamicprogramming @only4 Memory Saving Tip: You don't need the whole array. You could just use two variables for calculating the factorial. answered 22 Dec '16, 17:27

And for factorial here's the code
include <iostream>include <cstdlib>define ll long longusing namespace std; int result[1000] = {0}; ll fact_dp(int n) {
} answered 22 Dec '16, 17:24
@only4 your program fails for larger values. Even after changing ints to long long it works only till 20.
(22 Dec '16, 17:36)
I don't think finding factorial of integers > 10^14 is possible. I thinks it's a typo.
(22 Dec '16, 17:39)
@only4 why not have a look at https://blog.codechef.com/2009/07/02/tutorialforsmallfactorials .
(22 Dec '16, 17:43)
2
I think you program is same as using 2 variables for finding factorial.
(22 Dec '16, 17:44)

@nikhil_chandak Yes but I think calling the function again and again takes more time than this, so this is time efficient. Please correct me if I am wrong. answered 22 Dec '16, 17:37

@only I didn't mean recursion. I meant:
I have removed the if clause. Hope this helps :) If you didn't understand, feel free to ask me! answered 22 Dec '16, 17:45

You could speed up the multiplication by using karatsuba method for multiplication of large numbers. But multiplication is already assumed to be O(1). So for factorial I don't think you can do better than O(n) whether you use dynamic programming or not. Using dp you can just avoid recalculation of factorials, but you have to build the factorial table in linear time first. That's the best you can do. So in 1 sec, If you want the factorial 20! in C,C++ ; (10^5)! in python If you want modular factorial (10^7)! in C C++ python (that's the best you could do) answered 22 Dec '16, 19:10

sorry that was a typing mistake.