Временная сложность алгоритма: найти длину самой длинной палиндромной подстроки

Я написал небольшую PHP-функцию, чтобы найти длину самой длинной палиндромной подстроки строки. Чтобы избежать многих циклов, я использовал рекурсию.

Идея алгоритма состоит в том, чтобы циклически проходить по массиву и для каждого центра (включая центры между символами и на символе) рекурсивно проверять значения левой и правой частей каретки на равенство. Итерация для конкретного центра заканчивается, когда символы не равны или одна из кареток находится вне диапазона массива (слова).

Вопросы:

1) Не могли бы вы написать математические вычисления, которые следует использовать для объяснения временной сложности этого алгоритма? В моем понимании это O (n ^ 2), но я изо всех сил пытаюсь подтвердить это подробными вычислениями.

2) Что вы думаете об этом решении, какие-либо предложения по улучшению (учитывая, что оно было написано за 45 минут только для практики)? Есть ли лучшие подходы с точки зрения сложности времени?

Чтобы упростить пример, я отбросил некоторые проверки ввода (подробнее в комментариях).

Спасибо, ребята, ура.

<?php
/**
* Find length of the longest palindromic substring of a string.
*
* O(n^2)
* questions by developer
* 1) Is the solution meant to be case sensitive? (no)
* 2) Do phrase palindromes need to be taken into account? (no)
* 3) What about punctuation? (no)
*/

$input = 'tttabcbarabb';
$input2 = 'taat';
$input3 = 'aaaaaa';
$input4 = 'ccc';
$input5 = 'bbbb';
$input6 = 'axvfdaaaaagdgre';
$input7 = 'adsasdabcgeeegcbgtrhtyjtj';

function getLenRecursive($l, $r, $word)
{
if ($word === null || strlen($word) === 0) {
return 0;
}

if ($l < 0 || !isset($word[$r]) || $word[$l] != $word[$r]) {
$longest = ($r - 1) - ($l + 1) + 1;
return !$longest ? 1 : $longest;
}

--$l;
++$r;

return getLenRecursive($l, $r, $word);
}

function getLongestPalSubstrLength($inp)
{
if ($inp === null || strlen($inp) === 0) {
return 0;
}

$longestLength = 1;
for ($i = 0; $i <= strlen($inp); $i++) {
$l = $i - 1;
$r = $i + 1;
$length = getLenRecursive($l, $r, $inp); # around char
if ($i > 0) {
$length2 = getLenRecursive($l, $i, $inp); # around center
$longerOne = $length > $length2 ? $length : $length2;
} else {
$longerOne = $length;
}
$longestLength = $longerOne > $longestLength ? $longerOne : $longestLength;
}

return $longestLength;
}

echo 'expected: 5, got: ';
var_dump(getLongestPalSubstrLength($input));
echo 'expected: 4, got: ';
var_dump(getLongestPalSubstrLength($input2));
echo 'expected: 6, got: ';
var_dump(getLongestPalSubstrLength($input3));
echo 'expected: 3, got: ';
var_dump(getLongestPalSubstrLength($input4));
echo 'expected: 4, got: ';
var_dump(getLongestPalSubstrLength($input5));
echo 'expected: 5, got: ';
var_dump(getLongestPalSubstrLength($input6));
echo 'expected: 9, got: ';
var_dump(getLongestPalSubstrLength($input7));