Временная сложность алгоритма для нахождения всех возможных слов телефонных цифр
Я изучаю эту проблему.
http://www.geeksforgeeks.org/find-possible-words-phone-digits/
По моему мнению, временная сложность должна быть O(n^2), но там упоминается, что временная сложность для их алгоритма составляет O(4^n). Почему это 4^n?
Какова будет космическая сложность?