title: Memoization algorithm time complexity
body: <p>I read this article <a href="http://thenoisychannel.com/2011/08/08/retiring-a-great-interview-problem/" rel="noreferrer">Retiring a Great Interview Problem</a>, the author came up with a <code>work break</code> problem and gave three solutions. The efficient one uses <code>memoization</code> algorithm and the author said its worst case time complexity is <code>O(n^2)</code> since <code>the key insight is that SegmentString is only called on suffixes of the original input string, and that there are only O(n) suffixes</code>.</p>
  
  <p>However, I find it difficult for me to understand why it is <code>O(n^2)</code>. Could someone please give me a hint or proof?</p>
  
  <pre><code>Work Break Problem: 
      Given an input string and a dictionary of words,
      segment the input string into a space-separated
      sequence of dictionary words if possible. For
      example, if the input string is "applepie" and
      dictionary contains a standard set of English words,
      then we would return the string "apple pie" as output.
  </code></pre>
  
  <p>The memoization algorithm from 
  <a href="http://thenoisychannel.com/2011/08/08/retiring-a-great-interview-problem/" rel="noreferrer">Retiring a Great Interview Problem</a></p>
  
  <pre><code>Map&lt;String, String&gt; memoized;
  
  String SegmentString(String input, Set&lt;String&gt; dict) {
        if (dict.contains(input)) 
            return input;
        if (memoized.containsKey(input) {
            return memoized.get(input);
        }
        int len = input.length();
        for (int i = 1; i &lt; len; i++) {
            String prefix = input.substring(0, i);
            if (dict.contains(prefix)) {
                String suffix = input.substring(i, len);
                String segSuffix = SegmentString(suffix, dict);
                if (segSuffix != null) {
                    return prefix + " " + segSuffix;
                }
            }
        }
        memoized.put(input, null);
        return null;
  }
  </code></pre>