Predict the time complexity of the following recursive function, given the vector is of size N and the initial call is calSum(v, 0).
int sum = 0;
void calcSum(vector v, int i)
{
if(i == v.size())
return;
sum += v[i];
calcSum(v, i+1);
}
Time complexity
@ankush
The vector was not passed by reference, Therefore on each function call, a fresh copy of vector is created resulting in overall complexity of O(n^2).
Demo :
run this code. One time without & and one time with &
It gets internal error because of memory limit exceeded
Success #stdin #stdout 0s 4508KB
done //Time for 1e4 with &
Success #stdin #stdout 0.12s 394624KB
done //Time for 1e4 without &
look at the memory used in both the cases
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.