GATE CSE
First time here? Checkout the FAQ!
x
0 votes
305 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 (193 points)   | 305 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

+10 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 (34k 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 (50.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 Aug 2017
  1. ABKUNDAN

    4670 Points

  2. Bikram

    4556 Points

  3. akash.dinkar12

    3420 Points

  4. rahul sharma 5

    3124 Points

  5. manu00x

    2864 Points

  6. makhdoom ghaya

    2450 Points

  7. just_bhavana

    2136 Points

  8. Tesla!

    2042 Points

  9. stblue

    1930 Points

  10. joshi_nitish

    1686 Points


24,970 questions
32,072 answers
74,567 comments
30,150 users