17.8 bedbathandbeyond.com complexity

#1

Hi guys,

you write that the time complexity is O(n^3):

For each k we can check for each j < k whether s(j+1,k) is a valid word and each such check requires O(k-j) time.

Do you mean that building substring takes O(n) time? Because the check itself is O(1) due to hash table, that’s why it’s not clear to me.

0 Likes
#3
0 Likes
#4

Changing j from k-W to k-1 would make the substring O(W) and the j loop O(WW).
Fixing the first substring to be from max(i-W,0) to i would make that loop O(W).
This would make the algo O(nWW), not O(nn*W).

0 Likes
#5

Applying Rabin Karp would take the complexity O(nW)?

0 Likes