Объяснение временной сложности следующего алгоритма

Question

У меня есть следующий алгоритм:

def func(n):
    if n <= 1:
        return 1
    x = 0
    for i in range(n ** 2):
        if i % 4  == 0:
            x += i
    return x + func(n//3) + func(n//3) + func(n//3)

Анализ сложности:

$ T (n) = n ^ 2 + 3 * T (\ fra c {n } {3}) + 1 $

Я знаю, что сложность составляет $ O (n ^ 2) $, но мой вопрос, как это возможно, что без рекурсивных вызовов и с ними сложность такая же ? Есть ли интуитивное объяснение этому?

Answer 1

Сложность алгоритма - это время / пространство самой дорогой операции. Если другие операции менее затратны по сравнению с ним, они не влияют на сложность алгоритма.

Например, если алгоритм выполняется в T(n) = n^2 + log(n) -> O(n)=n^2, поскольку log(n) не повлияет на n^2, так как он слишком много ниже, чем переменная n увеличивается.

Даже если T(n) = n^2 + 3n^2 = 4n^2 -> O(n)=n^2, потому что скаляр 4 не выведет сложность на другой количественный уровень, как зависимость переменная n (самая важная и дорогая часть) равна.