C++ STL Quiz 2 Question: 3

#1

Shouldn’t the time complexity of the code be O(N)? Please help me understand why it is mentioned as O(N^2)?

#2

Please paste the question here.

#3

The code:

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

#4

Assumming vector is defined as vector< int > v
Its time complexity will be O(n^2) because total n calls will be there and on every call vector gets copied to new vector which is O(n) for each call .Therefore O(n^2) for n calls. If the vector was passed by reference using & operator…then complexity would be O(n)

2 Likes