递归函数的运行时

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)。