c - 我如何继续计算此函数 (f3) 的时间复杂度？

Question

答案是 O(n^6) 但我不太确定如何到达那里，尝试使用较小的数字表明 g 将数字 n 提高到 3 的幂所以 k=n^3 因此 k^2=n^6(我认为)，但我如何用数学方式展示它，具体来说，我们被教导了一种使用新函数的方法T(n) 但我不确定如何在这里应用它，感谢任何帮助。

int g(int n)
{
    if (n <= 1) return 1;
    return 8 * g(n / 2);
}


void f3(int n)
{
    int k = g(n);
    for (int i = 2; i < k * k; ++i)
        {  printf("*");  }
} 

Answer 1

我们先来分析函数g(n):

g(n) = 8 * g(n/2)

如果你消除递归，这分解为

g(n) = 8^log_2(n)

并消除对数 yield :

g(n) = n^3

现在 k*k 是 n^3*n^3 = n^6，所以循环打印 n^6 个星号。这导致 O(n^6) 的时间复杂度。