About time complexity

#1

//Sir How the time complexity is 0(n^2) instead of O(n)?

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

#2

Hello @yashme7125 is it the complete code?
if this is the only code then for sure the time complexity should be O(N) only.
please confirm.

1 Like
#3

Yes Sir this is exact code in STL quiz 2 the answer was showing O(n^2) the answer of the question was wrong

#4

Hello @yashme7125 yes i have checked and the answer will be O(N^2) because the vector here is passed by value so it will need another time to be copied so that is why the answer is O(N^2):
if you still have any doubt you can ask here;
Happy Learning!!

#5

So sir it means for copying elements in vector it is taking additional O(n) time?

#6

Yes everytime when there is a call it have to do this for the length of the vector at that time.
so that is why it is O(N^2) .
if you have any doubt you can ask here:
Happy Learning!!

#7

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.