Троичный поиск в худшем случае

Скажем, у нас есть n ключей не фиксированной длины и алфавит длины k. Какова наихудшая временная сложность поиска в дереве троичного поиска? Конечно, худшим случаем будет длина самого длинного ключа, но как бы это выразить в терминах большого О?