double foo(int n){ int i; double sum; if(n==0) return 1.0; else for(i=0;i<n;i++) sum+= foo(i); return sum } What I have done: When function is called, the activation record is created on the call stack. For foo(n) let the size of AR be x. foo(0) does not place any recursive calls. foo(1) places 1 recursive call. Terminates at foo(0) foo(2) places 2 recursive calls to foo(0) and foo(1). foo(1) places another recursive call. Therefore total calls placed is 2+1. foo(3) places 3 recursive calls to foo(0),foo(1) and foo(2). Therefore total calls placed is 3+0+1+3= 7 recursive calls. foo(4) places 4 recursive calls. 4+0+1+3+7= 15. so we can see foo produces calls in the pattern: 0,1,3,7,15,31,… This shows us that foo(n) produces (2^n)-1 recursive calls. If we count the total no. of recursive calls made by foo(n) it becomes a geometric series and evaluates to approximately (2^n)-n. Hence I am getting Space complexity to be O(2^n). However several books have merely listed the answer as O(n!) without giving an explanation. I just want to know where I am going wrong in my approach.
Asked By : Sagnik
Answered By : WhatsUp
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/44591 Ask a Question Download Related Notes/Documents
