Fast Implementation Time Complexity Evaluation

The time complexity T(n) of the implementation model described in
Section 3.1.1 depends on the time complexity of the priority queue operations. The pseudo code of the algorithm is available in Appendix A, Section A.1. Let n denotes the number of elements in a priority queue. The following notation is used:

• PQInsert(n) is the function describing the asymptotic time complexity of the insert an element operation of the priority queue.
• PQDeleteMin(n) is the function describing the asymptotic time complexity of the delete minimum element operation of a priority queue.
• PQDelete(n) is the function describing the asymptotic time complexity of the delete an arbitrary element operation of a priority queue.
• PQMerge(n) is the function describing the asymptotic time complexity of the operation merging two priority queues.

The time complexity of the initialization in Phase I is:

T(n)_{Initialization}= n + nPQInsert(n)

The most expensive scenario of the main loop of the Combination phase of the algorithm is the case of combining two terminal nodes:

$T(n)_{MainLoop} \leq n (PQDeleteMin(n) + 4PQDelete(n)$
+3PQMerge(n) + PQInsert + c₂)

If the priority queue data structure chosen supports operations with the asymptotic time $O( \lg n)$ then the time complexity of Phase I is:
T(n) = T(n)_{Initialization} + T(n)_MainLoop
$T(n) = c_1n\lg n + c_2n \lg n + c_3n + c_4 \leq c_5n \lg n$
$T(n) = O(n \lg n)$;

The units of space required by the data structures in Phase I are:

S(n) = 6n = O(n)