# Confused about complexity. Any perspectives?

• Often when working on these problems, I come up with a naive approach first. In this case, I thought of a recursive, two-pointer approach:

``````bool isPalindrome( ListNode* t ) {
print(t);
// empty and singleton lists are Palindromes
if ( t == NULL || t->next == NULL )
return true;

ListNode *start, *n2l;
start = n2l = t;

while (n2l->next->next != NULL)
n2l = n2l->next;

if ( t->val != n2l->next->val )
return false;

delete n2l->next;
n2l->next = NULL;

return isPalindrome( t->next );
}
``````

When trying to analyze the time-complexity (for self-edification), I though this approached looked quadratic, basing my idea that it's kind of equivalent to a nested for-loop like

``````for (int i = 0; i < n; i++) {
for (int j = i; j<n-1-i; j++) {
// stuff
}
}
``````

However, if that perspective is correct, `// stuff` is performed n times, which would make it O(n) time-complexity. Of course, OJ says TLE. Can anyone help me understand my confusion? Is there some extra time I'm not accounting for in the recursive call? I am a newbie, so forgive me for being ignorant.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.