Find the Space complexity of following Code [Ace Gate Practice Booklet Vol-1 Page 127]

Question

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 ?

Comments

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

Answer 1

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)$. 

Comments

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?

Answer 2

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]

Comments

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.