Below is Kruskal's algorithm exactly as it appears in the course notes.

1  function KRUSKAL(G = (V, E))
2     sort(E, key((u, v)) = w(u, v))
3     forest = UnionFind.initialise(n)
4     T = (V, {})
5     for each edge (u, v) in E do
6        if forest.FIND(u) != forest.FIND(v) then
7           forest.UNION(u, v)
8           T.add_edge(u, v)
9     return T

It is run with slow union. Assume the following costs, and that every other line takes constant time:

The edge list is supplied to the algorithm already sorted by weight, so line 2 has nothing left to do; that is why it costs \Theta(1).

Assume the graph is connected and simple, which implies |V| - 1 \le |E| \le |V|^2.

Give the worst-case time complexity of the whole algorithm, and explain how you got it. A complete answer states the cost of each part, adds them up, and then says which term dominates and why. No space complexity is needed.

Since you cannot type \Theta(), please write theta() in your answer.