Worst Case Complexity Of efficient- Heap Solution will be greater than N^2

[rohgpt]

//***********************Following Code Can have time Complexity > N^2-------------------
for (auto it : adj[u]) {
int v = it.first;
int weight = it.second;
if (mstSet[v] == false && weight < key[v]) {
parent[v] = u;
key[v] = weight;
pq.push({key[v], v});
}
}

---

Above Code will keep pushing every weight and node if every time weight from the current node(that is 'u') is less than the weight previous.

So Let assume I have a weightage Complete graph, And We are Starting From Node 0, then for every last chosen MST NODE( that is 'u') => there will be K push operation in the priority queue, where K denotes no of node remaining from MST;

Initial priority Queue will have {{0,0}}

pop {0,0} from priority queue,
Put Node 0 in MST of Weight 0
Run Loop for child of NODE 0
->priority queue will push {1,1} { 5,2} {5,3}

Priority queue become {{1,1} { 5,2} {5,3}}

now it will pop {1,1}
Put Node 1 in MST of weight 1
Run Loop for child of NODE 1
->pq.push-> {3,2} {4,3}
Priority queue become {{5,2},{5,3},{3,2} ,{4,3}}

now it will pop {3,2}
put Node 2 in MST of weight 3
Run Loop for child of NODE 2
-> pq.push->{2,3}
Priority queue become {{5,2},{5,3},{4,3},{2,3}}

now it will pop {2,3}
push Node 3 in MST of Weight 2
Run Loop for child of NODE 3
-> No Push Operation
Priority queue become {{5,2},{5,3},{4,3}}

Now there will be an only pop operation that is 3-times pop then while(!pq. empty()) break out because priority queue becomes empty.

---

Now Generalizing Time complexity of above example for N Node.
So If we consider N Node Complete Graph such that for every new MST Node we will get the minimum distance for all remaining Node then
iteration 1 -> Push N-1 item in priority queues and Initial size of Priority Queue was 0
POP Minimum, Size become N-2
iteration 2 -> Push N-2 item in priority queues and Initial size of Priority Queue was N-2;
POP Minimum, Size become N-2+N-2-1=>2N-5;
iteration 3-> Push N-3 item in priority queues and Initial size of Priority Queue was 2N-5;
POP Minimum, Size become 2N-5+N-3-1=>3N-9;
iteration 4-> Push N-4 item in priority queues and Initial size of Priority Queue was 3N-9;
POP Minimum, Size become 3N-9+N-4-1=>4N-14;

.....So on till N-1 Iteration AtMax.

*****Push/pop of single element Time Complexity Of Priority Queue is LogN ************
computing Time Complexity of priority queue push operation from iteration 2
Time Complexity = (N-2)log(N-2)+ (N-3)log(2N-5)+ (N-4)log(3N-9)+ (N-5)log(4N-14) ..... + (1)log(NN-(N(N+3)/2)).

Now when we have all nodes visited in MST, then we will have an only Pop operation, Priority Queue will have NN-(N(N+3)/2) at last so Time Complexity will be poping all element NN-(N(N+3)/2) log( NN-(N(N+3)/2)).

So Overall Time Complexity will be Push Time Complexity+ Popping at End Complexity, Conclusion If We Solve Above Equation it Seems Like Time Complexity N^2 OR >N^2.

If I Did any mistake then let me know, But Please Dry Run Time Complexity for above shown Test Case, Sorry if I made any mistake
I hope u understood my doubt.