Doubt - less than 15 characters...change this thing

#1

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

What will be the time complexity for this?

#2

Hi @akhil54,

I am assuming initially i is 0,
It’s time complexity would be O(n) where n is the size of vector.

#3

Yes, exactly it should be O(n) but in vectors quiz, answer is O(n2). Can you check this?

#4

Quiz vector STL in Vectors topic

#5

@akhil54,

I am sorry I read the code wrong it should be O(n^2)

Here is the explanation:
vector v is not passed as a reference so, in each function call, it will create a new copy of the vector.
making a copy of vector is of time complexity O(n) (where n is the size of vector)

Now, lets see the function calls (assuming n = 3),

calcSum(v, 0) (creates a new copy of v)
calcSum(v, 1) (creates a new copy of v)
calcSum(v, 2) (creates a new copy of v)
calcSum(v, 3) (creates a new copy of v)
return back

Time complexity = (number of time function called)*(complexity of creating a copy) 
                =  (size of vector)*(N)
                =  O(N * N) 
                = O(N^2)

I hope it’s cleared now.

#6

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.

#7

I have given my review. Is’nt it showing?