GATE CSE
First time here? Checkout the FAQ!
x
0 votes
364 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 (207 points) 1 3 7 | 364 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 (34.8k points) 11 82 292
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 (56.9k points) 36 189 499
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.



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23338 Points

  2. Bikram

    17048 Points

  3. Habibkhan

    7912 Points

  4. srestha

    6228 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4968 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4286 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3794 Points


Recent Badges

Popular Question makhdoom ghaya
Popular Question junaid ahmad
Notable Question learner_geek
Notable Question jothee
Popular Question jothee
Notable Question Jeffrey Jose
Notable Question air1ankit
Nice Question jothee
Verified Human shaleen25
Popular Question jothee
27,290 questions
35,142 answers
83,920 comments
33,231 users