C++ 时间复杂度，用 for 循环表示递归函数的 Oh 表示法

Question

以下 Oh-Notation 函数的时间复杂度是多少？

void fun(int n)
{
if (n <= 1)
  return;
fun(n − 1);
for (int i = 0; i < n; i++)
  cout << " * ";
}

我假设它是 O(n)，但我可能错了

Answer 1

它是 O(n^2)，因为增加 n 会增加 for 调用的次数，以及每个 for 循环完成所需的时间。

两个变化呈线性上升，得到公式 O(n) * O(n) = O(n^2)。

Answer 2

没有递归会是O(n)。考虑 fun(3) 的调用堆栈：

fun(3): 
    fun(2):
       fun(1):
            return;
    cout " * * "
cout " * * * "

C++ Time complexity in Oh notation of recursive function with for loop