What will be the time complexity of this function (C++) and why? The function:

double sum1(std::vector&amp; v)
{    
    if (v.empty()) {
        return 0.0;
    }
    for(size_t i = 0; i &lt; v.size() - 1; ++i) {
        std::sort(v.begin()+i, v.end());
        v[i+1] += v[i];
    }
    return v.back();
}


There are n-1 sorts each one shorter by 1, so time taken by the function for n elements will be:

T(n) = C*n + n*log(n) + (n-1)*log(n-1) + ... + 2*log(2) + 1*log(1)


How to solve this polynomial? Or I missed something?
How to solve the polynomial: Clearly it's less than n * n * log (n) = O (n^2 log n). And clearly it is more than (n/2) * (n/2) * log (n/2) = O (n^2 log n). So it's n^2 log n. 

However, your assumption that the sort is O (n log n) is not justified. Each time except the first you are sorting an array that is already sorted with the exception of the first array element. Many sort implementations will sort that kind of array in O (n), so the total time may be just O (n^2).