ACCEPTED : mergesort cpp - auxillary space o(1) - time complexity o(nlongn)


  • 0
    L
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* merge(ListNode *a,ListNode *b)
        {
            ListNode * temp;
            if(!a)
             return b;
             if(!b)
               return a;
              
             if(a->val <=b->val)
                 {   
                     temp=a;
                     temp->next=merge(a->next,b);
                 }
              else 
               {   temp=b;
                   temp->next=merge(a,b->next);
               }
               
               
                return temp;
        }
              
        void half(ListNode *head , ListNode **a,ListNode **b)
        {
            ListNode *fast,*slow,*prev;
            slow=fast=head;
            while(fast && fast->next)
            {
                prev=slow;
                slow=slow->next;
                fast=fast->next->next;
            }
            *a=head;
            *b=slow;
            prev->next=NULL;
        }
            
        
       
        ListNode *sortList(ListNode *head) {
               if(!head)
                return NULL;
                if(!head->next)
                 return head;
                ListNode * a,*b;
                half(head,&a,&b);
                a=sortList(a);
                b=sortList(b);
                return merge(a,b);
        }
    };

  • 0
    L

    Thanks @Shangrila , i have taken care of your note in my next post for nqueens solution. :)


  • 0

    this solution is actually O(n^2) time and O(n) space. the merge function will be called (n/2+(n/2-1)+(n/2-2)+...+1)*2 times, so it's O(n^2) time. additional O(1) space for each merge call, the max stack depth would be n/2, so it's also O(n) space.


  • 0
    L

    I think it is O(nlogn) :

    ListNode *sortList(ListNode *head) {

    //called for every half of the list : height of tree, if each recursive call is treated as mother //child node = logn

           if(!head)
            return NULL;
            if(!head->next)
             return head;
            ListNode * a,*b;
            half(head,&a,&b);   // O(n)
            a=sortList(a);            
            b=sortList(b);
            return merge(a,b);   // O(n)
    

    }
    therefore : O(time for each level of the recursive call tree * no. of levels)
    =O(n*logn)

    2)Auxillarys space complexity is O(1) : If you observe in the merge function,temp is just a reference pointer pointing to already allocated memory i.e. the parent list itself,their is no extra allocation of memory at all.
    This is the reason i said auxillary space(space taken excluding the problem data space) is O(1) but space complexity(space taken including the problem data space) is still O(n) ,their is a difference between the both.Though in general when people talk about space complexity in algorithm analysis , people actually refer to the auxillary space complexity.


  • 0

    I think you are right about O(nlogn) as I didn't notice the recursive call of sortList(). However the auxiliary space complexity you are talking about seems meaningless as when we are considering complexity, we usually talk about the overall complexity other than partial complexity. of course, we get the overall complexity by accumulating the parts. therefore, the O(1) space mentioned by the problem is definitely overall complexity.


  • 0

    sorry I was wrong about space usage for merge function. the overall space complexity is O(logn) not because the temp pointer within merge function, it's actually because the two pointers, the head parameter and the return value within sortList function. every time the function is called, these data are pushed to the stack which takes up space.


  • 0

    sorry again but the overall space complexity is still O(n) because the merge function goes that deep.


  • 0

    after some search, I see that auxiliary space is space complexity minus space taken by the input. see this: http://functionspace.org/topic/241/Difference-between-space-complexity-and-auxiliary-space-
    therefore, auxiliary space used by your code is still O(n).


  • 0
    L

    I have already mentioned the difference between auxiliary space and space complexity in my first comment.
    I am not allocating new memory in any of the driver functions and neither is any space used up in the recursive stack because all that my recursive function is doing is to change pointer values.So auxiliary space is O(1).


  • 0

    thanks for your reply. a pointer usually occupies 4 bytes. every time merge() being called, pointer a, b and temp are pushed to the calling stack. these bytes are not considered as input, therefore must be accumulated to auxiliary space.


  • 0
    Y

    mzchen is right. The space complexity of your solution is not O(1). Strictly speaking, as long as there are recursion call involved in, the auxiliary space complexity can not be O(1) because of the memory cost of function calls.


  • 0
    L

    Yes ,i admit that the auxillary space is not 0(1) , it is 0(n).Thankyou @mzchen and @yuanliay to make things clear and pointing out my error


Log in to reply
 

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