GATE CSE
First time here? Checkout the FAQ!
x
0 votes
266 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)   | 266 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 (48.4k 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 Jun 2017
  1. Bikram

    3704 Points

  2. Hemant Parihar

    1502 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1416 Points

  5. Niraj Singh 2

    1391 Points

  6. Debashish Deka

    1246 Points

  7. Rupendra Choudhary

    1194 Points

  8. rahul sharma 5

    1158 Points

  9. Arjun

    956 Points

  10. srestha

    950 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Bikram

    1960 Points

  2. Niraj Singh 2

    1386 Points

  3. junaid ahmad

    502 Points

  4. Debashish Deka

    414 Points

  5. sudsho

    410 Points


23,373 questions
30,079 answers
67,405 comments
28,396 users