Why the TC is N^2 in this case?

#1

Why the TC is N^2 in this case?

#2

Which question you are talking about can you share the question also ?

#3

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);
}

O(N)

O(N^2)

Depends upon the compiler, but O(N) in most cases.

Depends upon the compiler, but O(N^2) in most cases.

#4

Because we are passing vector by value
So evry time vector is copied hence time complexity is O(n^2)

#5

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.

#6

Where are we passing vector as reference, it is passed as value

#7

Yes I corrected my statement just after Posting

#8

But if we pass it as value then only the reference of the vector will be changed and not everything in my sense.

#9

No if we pass vector by value it copied whole vector
Hence 0(n) extra time in coping the vector required

#10

You can also verify it by passing a vector to function and make Changes in it but they will not reflected in main

If it is pass by value

#11

If we pass vector from main to some function and perform constant operations in that function then the TC is O(1)

#12

Only if vector is passed by reference
If it is passed by value the. Coping will take 0(n) extra time

#13

yes the changes won’t reflect in main but isn’t that only v’s (in the question) reference is changed and point to the newer memory?

#14

Vector get copied
No reference in memory because they are not dynamically created

#15

I hope now your doubt resolved
So kindly give your feedback https://online.codingblocks.com/feedback/d/75473