Doubt in Google Kick Start 2018 Round A problem: Scrambled Words

Revision en1, by neeraj96, 2020-04-28 14:08:27

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) ?

Tags #googlekickstart, #doubt

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English neeraj96 2020-04-28 14:08:27 746 Initial revision (published)