Сложность алгоритма с известной сложностью подзадач

Question

Ввод алгоритма динамического программирования представляет собой одну, n длинную последовательность . Алгоритм рассматривает все возможные подстроки последовательности, а для длинной подстроки k вычисляет значение в O (k) времени.

Мне было интересно, если кто-нибудь скажет мне, как я могу оценить время работы этого алгоритма.

Answer 1

Хорошо, давайте копать.

7  abcdefg 
6  abcdef 
6  bcdefg 
5  abcde 
5  bcdef 
5  cdefg 
. 
. 
. 

OK, поэтому для строки длины n, мы имеем 2 подстроки длины n-1, 3 длины n-2 ..., n длины 1.