edited by
1,982 views
0 votes
0 votes
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 ?

edited by

2 Answers

Best answer
11 votes
11 votes

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

selected by
2 votes
2 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]

Related questions

1 votes
1 votes
2 answers
1
APOORV PANSE asked Jun 1, 2016
2,987 views
Consider the following c fragment : void DAA(n) { int i,j,k,x=0; for (i=1 ; i <=n ; i++) for (j=1 ; j <= i * i ; j++) { if ( j mod i == 0 ) for ( k = 1 ; k <= j ; k++) x=...
1 votes
1 votes
0 answers
2
Ankush Tiwari asked Jul 27, 2016
647 views
T(n)=sqrt(2T(n/2))+logn
0 votes
0 votes
2 answers
3
Shivam_j asked Oct 16, 2022
669 views
Class B network on the internet has a subnet mask of 255.255.119.0 what is maximum possible hosts per subnet. Assuming Classfull Addressing Scheme
2 votes
2 votes
1 answer
4