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:

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)

The average number of key comparisons done on a successful sequential search in list of length n is