Thread: Memoization

Hi guys, I know what's Memoization and how it's used in dynamic programming , but there's still something not understandable for me.

Memoization is primarily used for dynamic programming, for example in Fibonacci sequence we are calling much calls twice, so if we do an array with size n which can save every call that we called before and not to call it again, then we are declining the time complexity !

I understand that, but who said that the time of the calling function is greater than making an array and saving to it the calls? I mean:
without memoization, if I call F(1) once in left tree of recursive, then I will call it again in right tree, so we are calling twice F(1)
with memoization, if I call F(1) once in left tree of recursive, then I will no't call it again in right tree, I just save F(1) and use it again , in other words we are not "calling again F(1)" .

so I claim who said that not "calling again F(1)" will ofcourse reduce the time complexity? in other words why time complexity of using array that saves F(1) call will be smaller than calling F(1) itself?!

thanks alot

Originally Posted by laserlight

Did you do any research as to both the practical time cost of allocating an array and its possible time complexity? Did you write test programs to see which is faster as N becomes large?

You went ahead and just asked before doing your homework, didn't you? I know because I decided to search the Web for "time complexity of array allocation" and lo, there were essays written by other people that should have gone some way towards answering your question.

thanks ! I will try by myself once again, it's not homework ! I was reading the subject of dynamic programming and faced the subject of "memoization" , if you look back to my question, isn't about specific question it's general about "memoization" !

Originally Posted by Above article

Another key indicator for Help Vampires is the clearly stated but “impossible” question. These questions look reasonable on the surface, but in fact they are impossible to answer for a number of reasons. These questions include, for example, “How do I build a forum?” or “How can I make a chat site?”

A painfully accurate description of what's seen here. Imo the article makes a strong case for altogether removing such people, even if it offers examples of how to help the afflicted.