# 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.

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.