educative.io

Educative

It seems that the time complexity analysis of this problem is incorrectly stated as O(2^n)

The time complexity without memoezation is O(n^m) where n is the the size of the work bank and m is the length of the word. With memoezation it is O(n^2)

1 Like

Hello @Peter_Litvak,

We are using recursion in the solution so it always works with time complexity of O(n^2).
For example: If we have word abcd, it can be partitioned into abc and d only but if it was to be partitioned in any combination like abc/bac/cab then it would result in O(n^m).

Hmm, I don’t think it is correct, please take a look at the explanation of the problem here.

At about 2:28:30 time mark