Most of the time is spent doing fine collisions with shapes coming out of an R-tree to build up a connection graph.
For the vast majority of designs, it's fast. For very dense, imported designs, it can get slow. (No two tools keep data in the same form, so translating leads to inefficiencies.)