Time complexity

#1

how it will be n^2…?

#2

@sushant15
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

#3

wow…nice one…Just by adding ampersand, we can decrease the time complexity by root under n.
Thanks a lot bhaia.

#4

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.