Time complexity doubt

#1

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

}

time complexity will be O(N) , it will work each time for each element ???

#2

hi @mehul.narendra.dubey, the time complexity for this problem should be O(n^2) , since the function is called by value thus at each call the vector will be copied to v and since copying vector of size n takes o(n) time and n function calls will result in time complexity being o(n^2)

if vector have been passed by address or reference then the time complexity would have been O(n)

1 Like