Complessità temporale dell'algoritmo di Prim

Question

C'è questo algoritmo Prim che sto studiando, la cui complessità temporale è $ o (n^2) $ (nella matrice di adiacenza).

Per quanto ho capito, questo perché dobbiamo ckeck di tutti i nodi per ogni nodo, cioè quando si controlla il miglior vantaggio del primo nodo, dobbiamo controllare i bordi dal nodo corrente a tutti gli altri nodi. Questo fa al massimo $ (N-1) $ bordi. Controlliamo questo per tutti i nodi, quindi sarebbero i bordi N*(N-1) da controllare al massimo.

Allora perché la complessità del tempo è $ o (n^2) $?

Inoltre, perché non consideriamo i bordi che creano un ciclo e perché non li consumiamo nell'algoritmo? Questo fa qualche differenza nella complessità temporale?