algorithm - Find kth largest element in an array, two different priority_queue solutions time complexity -

i'm interested in 2 solutions using priority_queue specifically. although both use priority_queue, think have different time complexity.

solution 1:

int findkthlargest(vector<int>& nums, int k) {         priority_queue<int> pq(nums.begin(), nums.end()); //o(n)         (int = 0; < k - 1; i++) //o(k*log(k))             pq.pop();          return pq.top(); } 

time complexity: o(n) + o(k*log(k))

edit: sorry, should o(n) + o(k*log(n)) pointing out!

solution 2:

int findkthlargest(vector<int>& nums, int k) {     priority_queue<int, vector<int>, greater<int>> p;     int = 0;     while(p.size()<k) {          p.push(nums[i++]);     }      for(; i<nums.size(); i++) {          if(p.top()<nums[i]){             p.pop();             p.push(nums[i]);         }      }      return p.top(); } 

time complexity: o(n*log(k))

so in cases 1st solution better 2nd?

in first case complexity o(n)+klog(n) not o(n)+klog(k) there n elements in heap. in worst case, k can large n, unbounded data o(nlog(n)) correct worst case complexity.

in second case, there never more k items in priority queue, complexity o(nlog(k)) , again unbounded data k can large n, o(nlog(n)).

for smaller k, second code run faster, k becomes larger first code becomes faster. made experiments, here results:

k=1000 code 1 time:0.123662 998906057 code 2 time:0.03287 998906057 ======== k=11000 code 1 time:0.137448 988159929 code 2 time:0.0872 988159929 ======== k=21000 code 1 time:0.152471 977547704 code 2 time:0.131074 977547704 ======== k=31000 code 1 time:0.168929 966815132 code 2 time:0.168899 966815132 ======== k=41000 code 1 time:0.185737 956136410 code 2 time:0.205008 956136410 ======== k=51000 code 1 time:0.202973 945313516 code 2 time:0.236578 945313516 ======== k=61000 code 1 time:0.216686 934315450 code 2 time:0.27039 934315450 ======== k=71000 code 1 time:0.231253 923596252 code 2 time:0.293189 923596252 ======== k=81000 code 1 time:0.246896 912964978 code 2 time:0.321346 912964978 ======== k=91000 code 1 time:0.263312 902191629 code 2 time:0.343613 902191629 ======== 

i modified second code little bit make similar code1:

int findkthlargest2(vector<int>& nums, int k) {     double st=clock();     priority_queue<int, vector<int>, greater<int>> p(nums.begin(), nums.begin()+k);      int i=k;     for(; i<nums.size(); i++) {         if(p.top()<nums[i]){             p.pop();             p.push(nums[i]);         }      }     cerr<<"code 2 time:"<<(clock()-st)/clocks_per_sec<<endl;     return p.top(); } int findkthlargest1(vector<int>& nums, int k) {         double st=clock();         priority_queue<int> pq(nums.begin(), nums.end()); //o(n)         (int = 0; < k - 1; i++) //o(k*log(k))             pq.pop();           cerr<<"code 1 time:"<<(clock()-st)/clocks_per_sec<<endl;         return pq.top(); }  int main() {      read("in");  vector<int>v;  int n;  cin>>n;  repl(i,n)  {      int x;      scanf("%d",&x);      v.pb(x);  }   for(int k=1000;k<=100000;k+=10000)  {      cout<<"k="<<k<<endl;     cout<<findkthlargest1(v,k)<<endl;     cout<<findkthlargest2(v,k)<<endl;     puts("========");   } } 

i used 1000000 random integers between 0 10^9 dataset, generated c++ rand() function.