# Time Complexity of reconstructing corrupted file

Suppose all the spaces between the words(only small letter alphabets and no punctuation) in a file has been deleted and we need to reconstruct the file. There is a dictionary available which answers whether a word is valid or not in O(1).

Brute force approach is to use backtracking i.e try out all the possibilities. Take for example: "donotsitonthefloor" I start from d, and check if "d" is in dictionary, if not i move ahead. then check for "do", it is a valid word, so i check whether "notsitonthefloor" can be split into valid words. And so on ..

Now coming to analyzing time complexity of this approach, the best i can come up with is:

$T(n) = \sum_{i=1}^n T(n-i) + O(n)$

1) Is the above equation correct? If so, is it possible to simplify it? (i suppose master's theorem can't be applied to this kind of equation).

2) Suppose if dynamic programming is used to store results of repeated calls, i.e. using an array to store whether input[i:n] is valid or not and checking first in this array before making a repeated call. What would be the running time after applying this optimization?