Tempo di esecuzione del caso peggiore dell'algoritmo di approssimazione del vertice minimo

Question

Considerando questo fattore $2$ Algoritmo di approssimazione di copertura vertice minima:

Ripeti mentre c'è un vantaggio:

Scegli arbitrariamente un bordo scoperto $ e = (u, v) $ e aggiungi $ u $ e $ V $ alla soluzione. Elimina $ u $ e $ V $ dal grafico. Infine, produce la copertura del candidato.

Voglio trovare il tempo peggiore di questo algoritmo. Dal momento che in un grafico completamente connesso abbiamo $ O (n^2) $ bordi, quindi il ciclo verrà eseguito al massimo $ O (n^2) $ volte.

Qui non sono sicuro di quale potrebbe essere il numero massimo di operazioni di eliminazione $ O (n^2) $ I bordi elaborati nel ciclo ci sarebbero uno scenario con un gran numero di operazioni di eliminazione contribuirebbero alla complessità complessiva.

Voglio dire ingenuamente che nel peggiore dei casi si moltiplica semplicemente il numero massimo di bordi possibili con il numero massimo di operazioni di eliminazione possibile (entrambe $ O (n^2)) $ dando $ O (n^4) $, Ma questo sembra sbagliato.

Eventuali intuizioni apprezzate.