Каков Большой O этой функции O (n ^ 3)?

Question

Я застрял в этой записи большого О о том, как это должно быть О (n ^ 3). Где мой мыслительный процесс пошёл не так?

Я знаю, что вложенным циклом for является O (n ^ 2) и что цикл while, вероятно, является функцией O (nlogn), поскольку цикл for является функцией O (n), а значение цикла while умножается на два, что делает его O (logn). При этом утверждается, что ответ O (n ^ 3), и я не понимаю, как это произошло, если рекурсивная часть функции не имеет к этому отношения?

def do_stuff2(n, x=1.23):
    if n <= 0:
        return 0
    val = 1
    for i in range(n//2):
        for j in range(n//4):
            x += 2*x + j/2 + i*1.2
    while val <= n:
        for i in range(n):
            x += val**2 + i//2
        val *= 2
    x += do_stuff2(n - 1, x/2)
    return x

Я считаю, что x не влияет на нотацию Big O, потому что она является константой, потому что она не используется при определении того, сколько раз цикл зациклится.

Итак, еще раз, я ожидал, что вывод функции будет O (n ^ 2), но фактический вывод будет O (n ^ 3)

Answer 1

Ваша функция имеет два вложенных цикла, это O(n^2):

for i in range(n//2):
    for j in range(n//4):
        x += 2*x + j/2 + i*1.2

Но, кроме того, ваша do_stuff2() функция принимает аргумент n и вызывает себя до n <= 0, то есть это еще один O(n).

Answer 2

посмотрите на последнюю строку функции: x + = do_stuff2 (n - 1, x / 2) это рекурсивный вызов. у вас есть n рекурсивных вызовов, каждый из которых O (N ^ 2), всего O (N ^ 3)