Can some body explain me how to apply memoization technique to achieve linear time complexity for bellow.


  • 1
    $\begingroup$ What makes you think it’s even possible? $\endgroup$ – Emil Jeřábek Jul 10 '14 at 12:17
  • $\begingroup$ It's certainly possible to use memoization, but you won't achieve linear time, the space requirements will be significant, and it's unclear that you'll get any benefit from memoization unless the same word lengths occur. $\endgroup$ – Rob Jul 10 '14 at 14:48

The linear time algorithms for this sort of problem are based on the SMAWK algorithm rather than more straightforward dynamic programming / memoization. I have an implementation of a linear-time line-breaking algorithm (possibly not exactly the one you want, but likely similar) in the Wrap.py module of my collection of Python algorithm implementations (you'll also need SMAWK.py).

| cite | improve this answer | |
  • $\begingroup$ is this solution is with motorization? pastebin.com/th13B9tt I cannot understand how to find k $\endgroup$ – Eshan Sudharaka Jul 10 '14 at 21:19
  • $\begingroup$ I don't understand your question. What is motorization? And what k do you want to find? $\endgroup$ – David Eppstein Jul 11 '14 at 6:06
  • $\begingroup$ Actually I want is to writing a recursive algorithm for word wrap problem and then extending the recursive algorithm to design a more efficient algorithm using memoization. As I understood recursive algorithms should call it self to solve the sub problem. But here it does not call same function. $\endgroup$ – Eshan Sudharaka Jul 11 '14 at 8:52
  • 3
    $\begingroup$ See Rob's comment above. You can do this, but you're very unlikely to get linear time that way. Why is the algorithm's architecture more important than its performance to you? $\endgroup$ – David Eppstein Jul 11 '14 at 16:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.