Vector STL Quiz doubt

#1

What i think that it shoul be O(n), not O(n^n).

#2

Hi sourabh,can you please send me the question

#3

Question 3 of Quiz Vector STL

#4

So you have the given function as :-

int sum=0;`

void calcSum(vector<int> v,int i){  // call by value
    if(i==v.size()){
        return ;
    }
    sum+=v[i];
    calcSum(v,i+1);
    return ;
}

you will notice that here function here is called by value
so every time you call the function then our original vector will be copied by the function and u know that copying a vector take O(n) so calling our function n times with subsequent copies will give us over all time complexity as O(n^2)
have the given function been like

int sum=0;

void calcSum(vector<int> &v,int i){ // call by reference 
    if(i==v.size()){
        return ;
    }
    sum+=v[i];
    calcSum(v,i+1);
    return ;
}

the time complexity would have been O(n)

In case of any doubt feel free to ask :slight_smile:
If you got your answer mark the doubt as resolved

#5

Alright, thanks a lot :slight_smile: