How is complexity O(N^2)?

#1

Each statement in calcSum takes O(1). In the last statement, it is a recursive call, hence calcSum will be called exactly n times for initial call of calcSum(v, 0). So how is the complexity O(N^2)?

#2

Hi @divyansh.shekhar,
Could you please share the question, I don’t have it.

#3

Hey @divyansh.shekhar,
please share the question.

#4

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.

#5

Question was: Predict the time complexity of the following recursive function, given the vector is of size N and the initial call is calSum(v, 0). Program starts here: int sum = 0; void calcSum(vector v, int i) { if(i == v.size()) return; sum += v[i]; calcSum(v, i+1); }

#6

Hi @divyansh.shekhar,
you can see there vector of size n is passed by value that mean copying of vector of size n is done in every call so its n^2

hope its clear now

#7

@divyansh.shekhar is the doubt clear? i’m marking it resolved.for now

#8

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.