Время выполнения рекурсивной функции

Question

Я пытаюсь найти время выполнения этой функции:

myst_fun_1([]) -> 0;
myst_fun_1(ListUsed = [_ | Tail]) -> length(ListUsed) + myst_fun_1(Tail).

Поскольку эта функция длины равна O(N) и myst_fun_1 вызывается N раз, время выполнения будет O(N^2)?Я хотел бы знать, правильно ли мое понимание.

Answer 1

myst_fun_1([]) -> 0;

myst_fun_1(ListUsed) -> 
    myst_fun_1(length(ListUsed), ListUsed).

myst_fun_1(Length, [_ | Tail]) ->
    Length + myst_fun_1(Length-1, Tail).

O (N)

Answer 2

length/1 - это BIF и будет работать намного быстрее, чем myst_fun_1/1, поэтому вероятность того, что O (N), чем O (N ^ 2), гораздо выше.