биномиальный коэффициент времени работы

Question

Я наткнулся на этот питон код , который вычисляет биномиальный коэффициент (n выберите k).Так как же время выполнения этого кода O (n)?

cache = {}
def bi(n, k):
    if (n, k) not in cache:
        if k == 0:
            cache[(n, k)] = 1
        elif n == 0:
            cache[(n, k)] = 0
        else:
            cache[(n, k)] = bi(n-1, k) + bi(n-1, k-1)
    return cache[(n, k)]

print(bi(9,9))