Time complexity of the following Prim's algorithm implementation

Question

What is the time complexity of the following code? I'm implementing prim's algorithm with adjacency matrix representation of the graph and priority queue. In my opinion, the time complexity is: the heap can grow at most to the size of (n-1), when the source is connected to every other node, and in the inner loop, the adjacency matrix is costing O(n), so in total: its O((n-1) * n) -> O(n^2), where n is the number of nodes. Is that calculation correct? So the heap is not improving my worst case runtime because of the adjacency matrix?

from graph import adj_mtx, AP
import heapq as hq

lv, visited, h = float('inf'), {}, []  # lv stands for 'large_value', h is the heap


def prims_mst(adj_matrix, src):
    hq.heappush(h, (0, (src, None)))  # O(logn)
    curr_dist = {item.value: lv if item.value != src else 0 for item in AP}  # AP is the enumeration of nodes

    while len(h) != 0:
        curr_nd = hq.heappop(h)[1][0]  # first element of the tuple is the value, second is the node  # O(1)
        visited[curr_nd] = True  # O(1)
        for nd, dst in enumerate(adj_matrix[src]):  # O(n) -> n is the number of nodes
            if nd not in visited and curr_dist[nd] > curr_dist[curr_nd] + adj_matrix[curr_nd][nd]:
                curr_dist[nd] = curr_dist[curr_nd] + adj_matrix[curr_nd][nd]
                hq.heappush(h, (curr_dist[nd], (nd, curr_nd)))  # O(logn)
        print h

What do you think the time complexity is, and why? We're not here to do your work for you. — Barmar

Catalin Catalin · Accepted Answer · 2017-07-12T16:27:44

It depends on what the len(h) does, what values it returns, and how the while behaves. When you find this out you multiply it with o(n) from the for and o(log n) from hq.headpush and you get your complexity It's something like O(x*nlog n) where X is the steps it takes for the while to finish.

Time complexity of the following Prim's algorithm implementation

1 Answers