TIME COMPLEXITY

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

The time complexity of the above code is O(N) clearly as there is only a single loop. Not O(n*n) . right ?

#2

yes true
sine u are iterating over the array just one
hence the overall complexity is O ( N )

EDIT:
On checking the other TA reply
It seems that because of pass by value the complexity increases. I`ll confirm once about the same and get back to u

#3

This is a question of your STL QUIZ-2 .And the answer mentioned is O( n*n) . Also in C++ STL QUIZ -1 there were incorrect answers. And I reported this to one of your TAS(Keshav Gupta) . Please look into it.

#4

@shahpankti931 its correct ans should be o(n*n) here explanation
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)

1 Like