Time Complexity of Text Justification with Dynamic Programming

Viewed 749

I've been working on a dynamic programming problem involving the justification of text. I believe that I have found a working solution, but I am confused regarding this algorithm's runtime.

The research I have done thus far has described dynamic programming solutions to this problem as O(N^2) with N as the length of the text which is being justified. To me, this feels incorrect: I can see that O(N) calls must be made because there are N suffixes to check, however, for any given prefix we will never consider placing the newline (or 'split_point') beyond the maximum line length L. Therefore, for any given piece of text, there are at most L positions to place the split point (this assumes the worst case: that each word is exactly one character long). Because of this realization, isn't this algorithm more accurately described as O(LN)?

@memoize
def justify(text, line_length):

    # If the text is less than the line length, do not split
    if len(' '.join(text)) < line_length:
        return [], math.pow(line_length - len(' '.join(text)), 3)

    best_cost, best_splits = sys.maxsize, []

    # Iterate over text and consider putting split between each word
    for split_point in range(1, len(text)):
        length = len(' '.join(text[:split_point]))

        # This split exceeded maximum line length: all future split points unacceptable
        if length > line_length:
            break

        # Recursively compute the best split points of text after this point
        future_splits, future_cost = justify(text[split_point:], line_length)
        cost = math.pow(line_length - length, 3) + future_cost

        if cost < best_cost:
            best_cost = cost
            best_splits = [split_point] + [split_point + n for n in future_splits]

    return best_splits, best_cost

Thanks in advance for your help, Ethan

1 Answers
Related