Longest palindrome substring in logarithmic runtime complexity

Question

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.

Answer 1

If a you are given a palindrome $p$ of size $N$ (as you say in the beginning of the question), then the longest palindrome is $p$ itself and you don't need to do any computation.

If your input is not a palindrome but an arbitrary string, then you need to at least read the input and therefore $\Omega(N)$ is a trivial lower bound.