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);
}
What should be the time complexity??
@duttrohan0302
hello rohan,
how vector is passed in function is it pass by value or pass by reference.
if it is passed by value (ie vector < int > v ) then time complexity will be O(n^2)
reason-> total n calls will be there and in each call old vector get copied to new vector which will take O(n) operation so in total n * n operation which is equivalent to O(n^2).
if it passed by reference(i.e vector < int > &v ) then simply O(n) because n calls and for each call O(1) operation so total n*1 operation which is equivalent to O(n)