educative.io

Time complexity of Word Break

Courses
,
#1

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
#2

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!!

#3

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
#4

@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

1 Like
#5

@Isaac_Haseley, yes I’d like to reiterate back to my previous response.

However, this substring is created up to the length of the input string, costing us O(n) time. So, as a result, the time complexity will be O(n^3).

Thank you for pointing this out!

1 Like