GATE CSE
First time here? Checkout the FAQ!
x
0 votes
250 views
Find the time and Space complexity of code below : 


void fun(n)
{
    if (n==1) then
    call A();
    else 
    {
        fun(n/2);
        fun(n/2);
        call B(n);
    }
}

Please note that B(n) takes O(n) time and A(n) takes O(1) time respectively.

Time complexity for above code would be : 

$T(n) = 2T(n/2)+O(n)$ which is $O(nlog(n))$

But What will be space complexity ?

asked in Algorithms by (189 points)   | 250 views
Dude do you pdf of this ACE book.?
No, I have purchased the book.. I hope its worth as I can find good questions to practice on Algorithms so far..
where to purchase that book ? please link

2 Answers

+9 votes
Best answer

Its clear that n is a number then it takes only $O(1)$ space. But As this function is recursive and its dividing n by 2  each time, hence it forms a $log n$ size stack in the memory for the execution.

Hence space complexity will be $O(log n)$. 

answered by Veteran (33.9k points)  
selected by
Is the space complexity independent of the same of B()?
Its mentioned in the question that B() takes O(n) timnes to solve the problem, If it taking extraw memory then it should also been mentioned the question. But its not there. Hence Its safe to assume that O(1).
@Arjun Sir this recursion seems like Merge Sort, thats wny we will force it to be merge sort, I think thats overthinking of the problem. Is not it?
+3 votes

assume A() as single line statement and B() as merge algorithm in merge sort which take O(n) time [ these two step does not increase the stack depth]

answered by Veteran (46.9k points)  
merge sort takes $O(n)$ space also rt?
/// template for mergesort outplace and using array//
void merge(array A,p,q) {
    allocate a new temp array of size n;
    merge the two segments of A using temp array;
    repace A with temp;
}
void mergesort(array A,start,end) {
    divide in mid;
    mergesort(A,start,mid);
    mergesort(A,mid+1,end);
    merge();
}
int main() {
    input array A[n];
    mergesort(A,0,n);//
}

In case of array :

except the original input array mergesort() procedure takes an extra O(n) space as a temporary storage and dominates over O(logn). So if we talk about extra space(excluding original array[n] in main function) YES, mergesort() takes linear stack space.

in case of linked list:

apart from the original linkedlist mergesort() does not allocate any new linkedlist or temporary space. So extra stack space is $O(logn)$

I was just making an analogy of B() to merge() procedure (not mergesort()) assuming  no extra space allocation.



Top Users May 2017
  1. akash.dinkar12

    3154 Points

  2. pawan kumarln

    1636 Points

  3. sh!va

    1590 Points

  4. Arjun

    1350 Points

  5. Bikram

    1298 Points

  6. Devshree Dubey

    1246 Points

  7. Angkit

    1044 Points

  8. Debashish Deka

    1042 Points

  9. LeenSharma

    880 Points

  10. srestha

    706 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    384 Points

  2. pawan kumarln

    262 Points

  3. Ahwan

    236 Points

  4. Arnab Bhadra

    136 Points

  5. LeenSharma

    118 Points


22,770 questions
29,090 answers
65,119 comments
27,635 users