Quiz-2 problem STL

#1

int sum = 0;
void calcSum(vector v, int i)
{
if(i == v.size())
return;
sum += v[i];
calcSum(v, i+1);
}

How is the time complexity of this function O(n^2). It should be O(N).

#2

hello @govilayush
its time complexity will be O(n^2).
because total n calls wiil be there and on every call vector get copied to new vector which is O(n) for each call . therefore O(n^2) for n calls

#3

So how can we make this O(N). Why does the vector gets copied? The function can use the existing vector.

#4

pass vector as refernce ,

ie vector &v;

now time complexity will be O(n) because we are passing vector as refernce

1 Like