Как мне go включить для вычисления временной сложности этой функции (f3)?

Question

Ответ O(n^6), но я не совсем уверен, как туда добраться, попытка с небольшими числами показывает, что число 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)

и исключит логарифм:

g(n) = n^3

Теперь k*k равно n^3*n^3 = n^6, поэтому l oop печатает n^6 звездочки. Это приводит к временной сложности O(n^6).