It could be as bad as N*M. If (M) is dense matrix, then this is (N)², so this algorithm ended up being in cubed again, but if it's a sparse matrix, so the number of edges is linear like in a planar graph, for example, then this is (N)² which is actually a lot better. 