Could someone explain me about the complexity of Trie and the algorithm of the distance of levenshtein? For tries my professor, has one image that says the complexity of it is O(k(logm +1)) where k is the key and m the quantity of distinct digits in alphabet for search, and for insert is O(k1 logm +k2m)where k1 is the length of the most common prefixes and k2 is the number of nodes that has to be included in the Trie, but I need the asymptotic complexity and in every place I search says that the complexity is O(k) for everything (insertion, delete and search) where k is the key...
And about the Levenshtein distance I used to make an algorithm to suggest similar words when people write something wrong suggest similar words like this in the image, and in some places I found that the complexity is O(n²) where n is the key and others that is O(n*m) where m is the length of the key (word) and n the Trie profundity...
here is my algorithm to suggest similar words
I just tried to search what is the complexity (asymptotic complexity), and I want to solve my doubts, like, what is the real theoretical average and worst case complexity for Trie (insert, search, remove) and levenshtein distance for suggest similar words.