Ускорить рекурсивную функцию с тремя вызовами

На собеседовании дана рекурсивная функция:

def g(n):
    if n < 3:
        return 1
    return g(n - 1) + g(n - 2) + g(n - 3)

Сначала нужно оценить сложность такой реализации, а затем переписать функцию так, чтобы она возвращала тот же ответ, но работала быстрее.

Сигнатура

def g_fast(n: int) -> int:

Пример

g_fast(10) -> 193

Follow-up с собеседования: как считать такие значения быстрее, чем за O(n), если n очень большое?