string f(string str, int pos){
if(pos == str.size()) return “”;
string ret = f(str , pos+1);
append character str[pos] to end ret
return ret;
}
Function f(string , integer) basically reverses the string passed to it as a parameter.
Suppose, if I pass f(“Ayush”,0) my O/P will be : hsuyA.
f(“PQRS”,2) : O/P : SR.
Time Complexity : O(N)
You can see that for each call O(N) memory is consumed.
Therefore Space Complexity : O(N^2).
Correct me if I am wrong 
1 Like
I didn’t understand this point, You can see that for each call O(N) memory is consumed. Therefore Space Complexity : O(N^2).
How the space complexity for each recursive call will be O(N).
@arpit728 - Strings are passed by value (i.e. copied again) in C and C++. So each call, worst case O(N) memory will be taken. He is assuming you are calling it N times, so O({N}^{2})
@guitarlover time complexity will also be \mathcal{O}(N^2). All the memory used is filled at runtime, so time complexity cannot be less than memory complexity here.
I doubt it!
Suppose we call f(string,0).
The function keeps calling itself with the same string but the integer argument is incremented by one. This process goes on until integer argument reaches gets to string.size().
f is called N times.
I feel it should be O(N).
Do you have any proof for O(N^2) ?
String is copied. Copying string takes additional O(N) time, which accounts for addition N factor.
Got it.
Thank you 