Confused about complexity. Any perspectives?

  • 0

    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 ) {
      // 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.

Log in to reply

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