Анализ асимптотической c сложности нисходящего подхода для решения проблемы самой длинной строки палиндроми c

Question

def length_longest_palindromic_substring(i, j, s, lookup):
    """Finds the length of longest palindromic substring in string s from index i through j

    i : Indicates the starting index in s of search space for palindromic substring
    j : Indicates the ending index in s of the search space for palindromic substring
    s : Actual string
    lookup : Dp table for storing already computed values to do a "careful" brute-force
    Note : Only returns the length of the string and not the actual string
    """
    if (i, j) in lookup:
        print('I got a hit in the lookup table')
        return lookup[(i, j)]

    if i == j:
        lookup[(i, j)] = 1
        return 1
    if j == i + 1:
        if s[i] == s[j]:
            lookup[(i, j)] = 2
            return 2

    # Check if the existing substring is already a palindrome
    k = i
    l = j
    while k <= l:
        if s[k] == s[l]:
            k += 1
            l -= 1
        else:
            break
    if l < k:
        lookup[(i, j)] = j - i + 1
        return j - i + 1

    # Guess a k in the given range and use that to recurse
    for k in range(i, j):
        computed_value = max(length_longest_palindromic_substring(i, k, s, lookup),
                             length_longest_palindromic_substring(k + 1, j, s, lookup))
        if (i, j) in lookup:
            if computed_value > lookup[(i, j)]:
                lookup[(i, j)] = computed_value
        else:
            lookup[(i, j)] = computed_value

    return lookup[(i,j)]


# Test code
s = "abcrotator"
lookup_dict = {}
print(length_longest_palindromic_substring(0, len(s) - 1, s, lookup_dict))

Может кто-нибудь помочь мне понять временную сложность кода, написанного выше? Большинство нисходящих подходов, данных для решения проблемы, делают рекурсию с (i + 1, j) и (i, j-1) и принимают Макс между этими двумя. Чем вышеупомянутый код отличается от этих подходов?

На мой взгляд, временная сложность составляет O (n ^ 3), что кажется столь же плохим, как и грубая сила. Тем не менее, я вижу, что некоторые вызовы функции "ищутся" из таблицы DP. Итак, я не могу обернуть голову, как это вырождается в грубую силу, даже с воспоминаниями?