Does Memoization improve the execution time of this algorithm?
"Given an array of n integers, return an array of your factorials."
Instead of a straight path to iterate over the array and find the factorial for each, I thought of a memoirized approach where I store the previously calculated factorials and use them in subsequent ones.
For example: 7! can be calculated very quickly if the result is 6! stored somewhere. However, I noticed that the execution time of both algorithms is still O (n). (I may be wrong) Does this imply that we are not speeding up the process here? If so, does that mean memoization is not useful in non-wood recursion problems? (In Fibonacci we effectively prune the recursion tree, keeping in mind the previously found values, in the case of the factorial we actually have no tree, more like a recursive ladder) Any comments are appreciated.
source to share
However, I noticed that the execution time of both algorithms is still O (n).
O-Notation hides the most important characteristic here. It takes into account the length of the array, not the size of the numbers, which is much more important when working with factorials.
You have to implement memoization with a hash table. If you do this, you get O (1) for each entry asymptotically.
source to share