Пытаюсь вычислить время выполнения моей функции

У меня есть этот код python для поиска самой длинной подстроки. Я пытаюсь вычислить асимптотическое время его выполнения, и я пришел к ответу, но я не уверен, что это правильно. Вот код: 

def longest_substring(s, t):
    best = ' '
    for s_start in range(0, len(s)):
        for s_end in range(s_start, len(s)+1):
            for t_start in range(0, len(t)):
                for t_end in range(t_start, len(t)+1):
                    if s[s_start:s_end] == t[t_start:t_end]:
                        current = s[s_start:s_end]
                            if len(current) > len(best):
                                best = current
    return best
Очевидно, что эта функция имеет очень медленное время выполнения. Именно так все и было задумано. Мой подход состоял в том, что поскольку существует цикл for с еще 3 вложенными циклами for, время выполнения примерно равно O(n^4). Я не уверен, что это правильно, потому что не каждый цикл повторяется над входом размер. Кроме того, предполагается, что s = t = n(входной размер). Есть идеи?
1 3
python asymptotic-complexity

1 ответ:

Если вы не уверены, что это O(n^5), попробуйте вычислить, сколько петель вы проходите только для строки s (т. е. внешние две петли). Когда s_start == 0, внутренний цикл выполняется n + 1 раз; когда s_start == 1, внутренний цикл выполняется n раз, и так далее, пока s_start = n - 1, для которого внутренний цикл выполняется дважды.

Сумма 

(n + 1) + (n) + (n - 1) + ... + 2

- арифметический ряд, для которого формула 

((n + 1) + 2) * n / 2

, что означает O (n^2).

Дополнительный фактор n исходит из s[s_start:s_end] == t[t_start:t_end], который является O(n).

2