educative.io

Time complexity of Word Break

The core loop from the optimized solution:

    for i in range(1, n+1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

The time complexity of this algorithm is O(n^2), where n is the length of the input string.

In the if-condition, we create a string s[j:i]. Does this add an additional O(n) complexity, bringing our total complexity to O(n^3)?

Additionally, on line 4, we create a set of words in word_dict. Should our total time be O(w + n^3)?


Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Solution: Word Break - Grokking Coding Interview Patterns in Python

1 Like

Hello @Isaac_Haseley,

Creating the substring within the if-condition, using slicing s[j:i] has a time complexity of O(1) per operation, as it simply creates a view of the original string without copying characters.

Regarding the creation of the set of words in word_dict on line 4, it indeed adds a one-time overhead of O(w) time complexity. However, this overhead is typically much smaller than the main loop’s complexity i.e. O(n^2).

Therefore, the total time complexity of the algorithm remains O(n^2), where n is the length of the input string.

Happy learning!!

Hey @Dian_Us_Suqlain!

It looks like string slicing in Python is O(k) where k is the length of the slice: TimeComplexity - Python Wiki

1 Like

@Dian_Us_Suqlain so to the original question, is the time complexity actually O(n^3)?


Course: Grokking Coding Interview Patterns in Python - AI-Powered Learning for Developers
Lesson: Solution: Word Break - Grokking Coding Interview Patterns in Python