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
Jun 2, 2016
in Algorithms
APOORV PANSE
849 views