<p>The linear time algorithms for this sort of problem are based on the <a href="https://en.wikipedia.org/wiki/SMAWK_algorithm">SMAWK algorithm</a> 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 <a href="http://www.ics.uci.edu/~eppstein/PADS/Wrap.py">the Wrap.py</a> module of my collection of Python algorithm implementations (you'll also need <a href="http://www.ics.uci.edu/~eppstein/PADS/SMAWK.py">SMAWK.py</a>).</p>

CC BY-SA 3.0
2014-07-10T21:19:44.790Z
is this solution is with motorization? http://pastebin.com/th13B9tt I cannot understand how to find k
Eshan Sudharaka
CC BY-SA 3.0
2014-07-11T06:06:09.167Z
I don't understand your question. What is motorization? And what k do you want to find?
David Eppstein
CC BY-SA 3.0
2014-07-11T08:52:49.770Z
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.
Eshan Sudharaka
CC BY-SA 3.0
2014-07-11T16:24:31.913Z
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?
David Eppstein
CC BY-SA 3.0
2014-07-10T19:05:24.540Z
2014-07-10T19:05:24.540Z
David Eppstein
<p>Can some body explain me how to apply memoization technique to achieve linear time complexity for bellow. </p>

<p><a href="http://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/" rel="nofollow">http://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/</a></p>

CC BY-SA 3.0
2014-07-10T12:17:38.167Z
What makes you think it’s even possible?
Emil Jeřábek
CC BY-SA 3.0
2014-07-10T14:48:16.290Z
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.
Rob
<dynamic-programming>
Liner time complexity for wordwrap problem
Eshan Sudharaka
# Liner time complexity for wordwrap problem

(Asked by: username_0 on 2014-07-10)

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

<http://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/>

**Tags:** dynamic-programming

> **Comments:**
> **username_1**: What makes you think it’s even possible?  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2014-07-10. Score: 6

The linear time algorithms for this sort of problem are based on the [SMAWK algorithm](https://en.wikipedia.org/wiki/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](http://www.ics.uci.edu/~eppstein/PADS/Wrap.py) module of my collection of Python algorithm implementations (you'll also need [SMAWK.py](http://www.ics.uci.edu/~eppstein/PADS/SMAWK.py)).

> **Comments:**
> **username_0**: is this solution is with motorization? http://pastebin.com/th13B9tt I cannot understand how to find k  
> **username_3**: I don't understand your question. What is motorization? And what k do you want to find?  
> **username_0**: 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.  
> **username_3**: See username_2'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?  

---

