Time Complexity Clarification

Question

With the following algorithm (from Leetcode):

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given s = "leetcode", dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

The naive solution is given as follows:

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return word_Break(s, new HashSet(wordDict), 0);
    }
    public boolean word_Break(String s, Set<String> wordDict, int start) {
        if (start == s.length()) {
            return true;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end)) {
                return true;
            }
        }
        return false;
    }
}

The time complexity is listed as O(n^n) because that's how big the recursive tree goes. I totally agree that the last level of the recursion tree has N^N elements, but doesn't the one before that level have N^(N-1)? So we're looking at N^N + N^(N-1) + N^(N-2)... resulting in a much higher time complexity correct?

hmmm, maybe make word_Break private? Also, N^N + N^(N-1) + ... is a geometric series which gives O(N^(N+1)) — meowgoesthedog

meowgoesthedog meowgoesthedog · Accepted Answer · 2017-08-03T12:55:46

Let's start with a simple recurrence relation for the upper bound of the time complexity function (i.e. assuming that it loops the whole way without finding a match):

Here i is start and N is s.length(). Each term corresponds to:

1st: Recursive calls to word_Break with start = end, where end is j
2nd: Call to wordDict.contains with a substring of length end - start + 1.

Now since wordDict is a hashset, this call is O(L) where L is the length of the input word (because we need to copy the substring and hash it)

Expanding:

(Last step from Wolfram alpha)

Which is totally different to what your source says.

As added support for my answer, lets do a numerical test:

uint64_t T(uint32_t N, uint32_t start)
{
   if (start >= N) return 1;
   uint64_t sum = 0;
   for (uint32_t end = start + 1; end <= N; end++)
      sum += (end - start + 1) + T(N, end);
   return sum;
}

Results:

N        T(N)
-----------------
1        3 
2        9 
3        22 
4        49 
5        104 
6        215 
7        438 
8        885 
9        1780 
10       3571 
11       7154 
12       14321 
13       28656 
14       57327 
15       114670 
16       229357 
17       458732 
18       917483 
19       1834986 
20       3669993 
21       7340008 
22       14680039 
23       29360102 
24       58720229 
25       117440484 
26       234880995 
27       469762018 
28       939524065 
29       1879048160 
30       3758096351 
31       7516192734 
32       15032385501 
33       30064771036 
34       60129542107

Log-scale plot of time complexity:

As you can see this is linear, which means that the time complexity is of the form a^N and not N^N.

By contrast, T(N) = O(N^N) would give the following plot:

Which is not linear and grows much faster (note the numbers on the vertical axis).

Time Complexity Clarification

3 Answers