Longest palindrome substring in logarithmic runtime complexity


In a palindrome of size N, the amount of candidates for the longest palindrome is N^2. Therefore, the information theoretic lower bound (IBT) should be lg(N^2), which is equivalent to a runtime complexity of lg(N).

By IBT I mean that if we use a comparison based algorithm and you think about a decision tree to apply it, the leafs of that tree will be all of the possibilities (N^2 leafs), therefore the height of that tree is lg(N^2). However, I was not able to find any algorithm that is able to solve this question in this runtime complexity; the best I have found is Manacher’s algorithm that solves the question in linear time.