educative.io

Educative

Why is time complexity O(N∗M∗Len)?

Not really sure about how the time complexity ends up as O(N∗M∗Len)

Hi,

Referring to the Java code:

The loop on line 12 runs O(N) times, where N is the number of characters in the given string. In each iteration, the loop on line 14 runs O(M) times, where M is the total number of words. In each iteration of this loop, we find a substring on line 17 which runs for O(Len) times, where Len is the length of a word.
Therefore, the total time complexity comes out to be O(N * M * Len).

1 Like

Hi…

how is it going to run O(n) times? Isn’t it only running str.length - wordCount * wordLength? and it won’t ever be equal to length of the string? and if number of characters does not mean length of the string then does it mean num of characters other than the words ?

You’re right that it won’t ever be equal to the length of the string. However, we are talking about the time complexity, a worst-case analysis. Therefore, the time complexity will be O(N) in the worst case.