Jaka jest złożoność obliczeniowa i pamięciowa dla tego algorytmu?

Ćwiczę leetcode przed zmianą pracy. Aktualnie rozwiązuje następujące zadanie:

Dla telefonu "1905" można wygenerować następujące mnemoniki ["1w0j", "1w0k", "1w0l", "1x0j", ....]. Mnemonik to jest jak zapisujemy numer telefonu za pomocą liter patrząc na klawiaturę w telefonie.

Wydziergałem następujący algorytm:

def phoneNumberMnemonics(phoneNumber):
    keypad = {
		'1': ['1'],
		'2': ['a', 'b', 'c'],
		'3': ['d', 'e', 'f'],
		'4': ['g', 'h', 'i'],
		'5': ['j', 'k', 'l'],
		'6': ['m', 'n', 'o'],
		'7': ['p', 'q', 'r', 's'],
		'8': ['t', 'u', 'v'],
		'9': ['w', 'x', 'y', 'z'],
		'0': ['0']
	}
	
    return generate(phoneNumber, 0, keypad)

def generate(phone_number, current_element, keypad):
	if current_element == len(phone_number):
		return ['']
	
	child = generate(phone_number, current_element + 1, keypad)
	result = []
	
	digit = phone_number[current_element]
	for letter in keypad[digit]:
		for c in child:
			new_memonic = letter + c
			result.append(new_memonic)
	
	return result

Algorytm działa poprawnie, ale nie potrafię policzyć O, zarówno jeśli chodzi o pamięć, jak i złożoność obliczeniową. Jest na sali ktoś kto potrafiłby mi to wytłumaczyć. Możliwe, że to jest bardzo proste i odpowiedź będzie 4^długość numeru) ale mam jakieś zaćmieni i nie potrafię sam sobie wytłumaczyć skąd to się bierze ani jaka jest prawidłowa wartość

n - długość numeru

Zauważ, że w ogólności, najgorsze wejście do zadania, to gdy numer składa się z samych siódemek i dziewiątek. Wobec tego, olejmy inne numery telefonów. Zawsze są 4 opcje.

Ułóżmy sobie równanie rekurencyjne na czas:

T(n + 1) = T(n) + 4^n * O(n)
           ^      ^     ^
           |      |     czas stworzenia stringa długości n+1 przez sklejenie go z cyferką
           |      tyle wyników będzie na liście child
           |
           czas wywołania rekurencyjnego: generate(phone_number, current_element + 1, keypad)

T(0) = 1 # stworzenie pustej listy

Widać z tego, że

T(n) = sum(4^k * k for k in range(1, n+1))

Wolfram alpha podpowiada, że wynik tej sumy to

4/9*(3*4^n * n - 4^n + 1)

Złożoność pamięciowa - nigdy nie przechowujesz naraz więcej niż 4^n stringów, każdy długości n. Więc sumarycznie to jest O(4^n * n), tak samo jak w przypadku złożoności czasowej.