Confused about complexity. Any perspectives?


  • 0
    M

    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.


Log in to reply
 

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