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