CODEWITHSUNDEEP
c++algorithmsortingtime-complexitybig-o
Leena
Leena

Reputation: 783

What is the Time and space complexity of sort() in C++ with custom comparator function?

Consider the following code-

 bool cmp(pair<string,int> &a, pair<string,int> &b) {
     return ((a.second > b.second) || (a.second==b.second && a.first<b.first));
 }

vector<pair<string,int>> v;

sort(v.begin(),v.end(),cmp);

For this case, what would be my complexity? Will it be O(nlogn) ?

Upvotes: 0

Views: 1229

Answers (1)

Manav Chhibber
Manav Chhibber

Reputation: 768

std::sort has time complexity: O(NlogN) custom comparisons.
But in your case the comparator function cmp also performs string comparison,

(a.second==b.second && a.first<b.first)

std::basic_string operator< has time complexity linear in the size of the strings.

Hence, worst case complexity is O(K*NlogN) char comparisons, where K is length of the string.

Upvotes: 5

Related Questions