educative.io

Time Complexity of part "b. Build the graph"

Courses
,
#1

When I look at part “b”, I see outer and inner for loops, where we compare words until we compare different characters.
It seems to me that in the worst case, the time complexity of that part will be O (N * length of the longest word).
This concludes to O (N * L), where L is the length of the longest word.

So my question is why the time complexity is only taking into consideration part “d” of the algorithm, i.e. O (V + N), and not the time complexity of part “b”?

Thanks

2 Likes
#2

Let’s think asymptotically

Yoou arre right.
The time Complexity is O(V+N) + O(N*L)

Let’s make L as constant max at 26. Assuming all lower case

Now the time complexity O(V+N) + O(26 N)
When N tends to infinity/or very large

It boils down to O (V+N) + O (N) ~ O (V + N)
If vertices are all constants then it boils down to O (N).

Hope this helped.
Cheers

1 Like
#3

Hi @Gaurav7 your explanation is correct but doesn’t take into consideration the first part of the algorithms for which we initialise the graph and the in_degree data structures.

The fact that the alphabet contains 26 characters is important for considering that variable as a constant but it doesn’t do the same when it comes to the words.

Look at this part:

  for word in words:
    for character in word:
      inDegree[character] = 0
      graph[character] = []

Word length is not bound by the length of the the alphabet and therefore we could have words that are infinitely long so we definitely need to take that into account when measuring the time complexity.

I would have therefore have to deduce that the time complexity is:

O(V + E) + O(N*W)

Where N is the number of words in the list and W is the length of the longest word.

2 Likes