Let G(V, E) an undirected graph with positive edge weights. Dijkstra's single-source shortest path algorithm can be implemented using the binary heap data structure with time complexity:

Suppose there are $$\lceil \log n \rceil$$ sorted lists of $$\left\lfloor {{n \over {\log n}}} \right\rfloor $$ elements each. The time complexity of producing a sorted list of all these elements is :
(Hint : Use a heap data structure)

The elements 32, 15, 20, 30, 12, 25, 16, are inserted one by one in the given order into a max Heap. The resultant max Heap is

If T₁ = O(1), give the correct matching for the following pairs:

List - I

(M) T_n = T_{n - 1} + n
(N) T_n = T_n/2 + n
(O) T_n = T_n/2 + nlog n
(P) T_n = T_{n - 1} + log n

List - II

(U) T_n= O(n)
(V) T_n = O(nlogn)
(W) T_n = O(n²)
(X) T_n = O(log²n)