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 ?