Могу ли я упростить анализ времени выполнения алгоритма с двумя переменными, если я знаю k <= n?

Question

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

def neat_algorithm(n, k):
    assert k <= n
    assert k > 0

    sum = 0

    for i in range(n):
        for j in range(n):
            sum += 1

    for i in range(n-k,n):
        sum += 1

На первый взгляд, этот алгоритм выглядит так, как будто его время работы составляет Θ (n ^ 2) + Θ (k), но он потерпит неудачу, если 1 ≤ k ≤ n, и наихудший случай произойдет, если k = n. Так как я знаю эти вещи о k, правильно ли говорить, что время наихудшего случая на самом деле равно Θ (n ^ 2) + Θ (n), точнее просто Θ (n ^ 2), или мне нужно оставить k в выписке времени выполнения?

Answer 1

В этом конкретном случае вы можете упростить Θ (n ² + k) = Θ (n ² ), поскольку k ≤ n ≤ n ², таким образом, n ² член доминирует.

В общем, вы не всегда должны заменять k на n в асимптотике c, даже когда 0