STL Quiz 2 doubt

#1

Q3. Vector STL#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.

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

#2

no man!
not at all
u have to guess it by seeing the program

here the time complexity will be O(N^2)
becuase the vector is passed by value hence a copy is made each time in the recursive call
and O(N) for iterating over the entire vector once

hence O(N^2)

#3

ohhhh. Each recursive call will take O(N) time, because it’s passed by vector. My bad. Understood.

#4

vector is passed by value so in each call there will be copy of vector which takes O(N) time
hence O(N) for each call

#5

got it…

1 Like
#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.