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

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

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

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