i fail to understand how this code works.
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);
}
its the question 4 in the quiz
Hello Mustafa, the code is taking O(n) time complexity.
See, this code is similar like we are passing an array instead of a vector and want to calculate the sum of all the nos.
So for ex. suppose I have a vector with
4 elements
3 6 7 1
int sum = 0;
void calcSum(vector v, int i)
{
if(i == v.size())
return;
sum += v[i];
calcSum(v, i+1);
}
Now we are calling calcSum(v,0) now see
calcSum(v,0) sum = 0
It will go and check if the idx == v.size()
if not then
sum += v[idx] that is v[0] // sum += 3
now it will call caclSum(v,1)
It will go and check if the idx == v.size()
if not then
sum += v[idx] that is v[1] // sum += 6 , so the total value of sum becomes 9
now it will call caclSum(v,2)
It will go and check if the idx == v.size()
if not then
sum += v[idx] that is v[2] // sum += 7 , so the total value of sum becomes 16
now it will call caclSum(v,3)
It will go and check if the idx == v.size()
if not then
sum += v[idx] that is v[3] // sum += 1 , so the total value of sum becomes 17
now it will call caclSum(v,4)
It will go and check if the idx == v.size() // but here it is true that v.size() is equal to idx then it will return from here
so you have traversed every element of the array once and checked for the value and calculated the sum. So overall it is O(n) time complexity.
I hope it is clear to you. In case it is clear to you pls mark it as resolve and provide the rating as well as feedback so that we can improve ourselves.
In case there is still some confusion pls let me know, I will surely try to help you out.
Thanks 
Happy Coding !!
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.