java - What is the time complexity of this priorityQueue

Question

I have the below code, I wanted to know what is the time complexity of this code when I am using PriorityQueue.

I have a listOfNumbers of size N

Queue<Integer> q = new PriorityQueue<>();
q.addAll(listOfNumbers);

while(q.size()>1) {
    q.add(q.poll()+q.poll()); // add sum of 2 least elements back to Queue
}

As per this post : Time Complexity of Java PriorityQueue (heap) insertion of n elements?

O(log n) time for the enqueing and dequeing methods (offer, poll, remove() and add)

Now how to calculate the time when I am adding the element back to Queue again.

question from:https://stackoverflow.com/questions/66064093/what-is-the-time-complexity-of-this-priorityqueue

Answer 1

The running time of your program is log(n) + log(n-1) + ... + log(1).

This is log(n!) (by repeated application of the log rule log(a) + log(b) = log(ab)).

log(n!) is Theta(n log n) see Is log(n!) = Θ(n·log(n))?

So your program runs in Theta(n log n) time.