Big-O of Kruskal/Prim Algorithm
def kruskal(graph):
    for v in graph.keys():      # &lt;- O(V)
        parent[v] = v
        rank[v] = 0

    edges = []
    mst = []

    # this for loop creates a list of all edges O(E)
    for outer_key in graph.keys():
        for inner_key, inner_weight in graph[outer_key].items():
            edges.append((inner_weight, outer_key, inner_key))

    edges.sort()    # &lt;- this is O(ElogE) and where the complexity comes from

    for edge in edges:
        weight, v, u = edge

        if find(v) != find(u):    
            union(v, u)           # &lt;- union-find, let's check this in a second
            mst.append(edge)
                                  # ... so the whole for loop is O(E*O(union))
    return mst



So, your overall complexity is O(ElogE + E*O(union))

Let's look at your union-find implementation:

def find(v):   # find with path compression
    if parent[v] != v:
        parent[v] = find(parent[v])

    return parent[v]


def union(v, u):    # union by rank
    root1 = find(v)
    root2 = find(u)

    if rank[root1] &gt; rank[root2]:
        parent[root2] = root1
    else:
        parent[root1] = root2
        if rank[root1] == rank[root2]:
            rank[root2] += 1


According to Wikipedia, this implementation is in O(inverse Ackermann(n)), so that means for the overall implementation we get

O(ElogE), which is purely driven by the sort, or as Wikipedia says

O(T_sort(E) + E*(inverse Ackermann(V)))

In other words, your kruskal algorithm is fine complexity-wise.

Your Prims algorithm is O(ElogE), the main driver here is the PriorityQueue. Notice that your loop will be called O(E) times, and the inner loop will only be called O(E) times in total. So the main driver is adding and retriveving stuff from the Priority Queue. The operations on the PriorityQueue are in O(logE), so O(ElogE) in total for the whole loop.