# Time complexity in the solution seems wrong to me

I guess it’s not O(m+n^2) but O(m+n) because there’s only one loop, we traverse the word and make 1 slice for 1 iteration. It would be O(m + n^2) if we had n slices on each iteration.

1 Like

Hi @Arseniy,
The first loop iterates over each element in the input list `lst` and inserts it into a hash table using the `insert` method. The `insert` method has an average time complexity of `O(1)` for a single element, and is called `m` times in this loop, giving a time complexity of `O(m)` for this loop.

The second loop in the `is_formation_possible` function is responsible for checking all possible substrings of the input word `word` to determine if it can be formed using the elements of the input list `lst`. The loop iterates over all possible split points in the word, which are the points between each pair of adjacent characters. For example, given the word “hello”, the possible split points are between “h” and “e”, between “e” and “l”, between “l” and “l”, and between “l” and “o”.

For each possible split point, the loop extracts the two substrings of the word that result from splitting it at that point. For example, if the split point is between “e” and “l” in the word “hello”, the first substring would be “h” and the second substring would be “ello”.

Next, the loop checks if each substring is present in the input list `lst` by performing a hash table search using the `search` method. If the substring is found in the hash table, a boolean variable is set to True indicating that the substring is present.

Finally, the loop checks if both substrings are present in the hash table by checking the boolean variables. If both are present, it returns True indicating that the input word can be formed using the elements of the input list.

The time complexity of this loop is `O(n^2)`, where `n` is the length of the input word `word`, because it iterates over all possible split points in the word, which is equal to the number of pairs of adjacent characters in the word, and there are `n-1` pairs of adjacent characters in a word of length `n`.

The total time complexity of the `is_formation_possible` function is `O(m + n^2)`, where `m` is the length of the input list `lst` and `n` is the length of the input word `word` .

I hope this helps

1 Like