neeraj96's blog

By neeraj96, history, 4 years ago, In English

See the problem at this link . I was going through the editorial for this problem.

Let X be the number of distinct word lengths in the dictionary. The editorial claims that since the number of distinct word lengths in the dictionary is $$$O(\sqrt{M})$$$. The time complexity is $$$O(N\sqrt{M})$$$. Is this correct?

Let the distinct word lengths be $$$l_1, l_2, ..., l_X$$$. Let $$$F_{l_i}$$$ denote the number of dictionary words having length $$$l_i$$$.

Shouldn't the time complexity be $$$\sum_{i=1}^{X} N \times F_{l_i} = N \sum_{i=1}^{X} F_{l_i} = N L$$$.

The time complexity should be O(NL) ?

  • Vote: I like it
  • 0
  • Vote: I do not like it