# Why O(NlogK) algorithm takes longer running time than O(NK) algorithm

• This solution avoid repeated multiplication, but the running time is 384ms, larger then the O(NK) algorithm

``````   class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
if (n <= 1) return 1;
vector<int> index(primes.size());
vector<int> uglyNumbers(n);
uglyNumbers[0] = 1;
using val_pair = pair<int, size_t>;
priority_queue<val_pair, vector<val_pair>, greater<val_pair>> pq;
for (int j = 0; j < primes.size(); ++j) {
if (uglyNumbers[index[j]])
pq.push(make_pair(primes[j]*uglyNumbers[index[j]], j));
}
for (int i = 1; i < n; ++i) {
if (!pq.empty()) {
auto top = pq.top();
pq.pop();
uglyNumbers[i] = top.first;
int j = top.second;
index[j]++;
pq.push(make_pair(primes[j]*uglyNumbers[index[j]], j));
while (!pq.empty() && pq.top().first == top.first) {
auto next = pq.top();
pq.pop();
j = next.second;
index[j]++;
pq.push(make_pair(primes[j]*uglyNumbers[index[j]], j));
}
}

}
return uglyNumbers.back();
}
};``````

• Same here for Java Solution, I think this is because it has the overhead of maintaining priority queue and constructing & destructing pairs, and also it has to deal with duplicates. All this will not have much performance gain for relatively small value of k

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.