At Most N Palindromes

$\Theta(n \log n)$, which is why the palindromic tree has $\Theta(n \log n)$ nodes and builds in $\Theta(n \log n)$: the fail tree has depth $\Theta(\log n)$.

At most $n$, which is why the palindromic tree has $O(n)$ nodes and builds in $O(n)$: appending one character adds at most one new palindrome.

$\Theta(n^2)$, which is why the palindromic tree has $\Theta(n^2)$ nodes and builds in $\Theta(n^2)$: in aaa...a every substring is a palindrome.

Exactly $2n$, which is why the palindromic tree has $O(n)$ nodes and builds in $O(n)$: appending one character adds one odd and one even palindrome.