We study the problem of critical slowing-down for gauge-fixing algorit
hms (Landau gauge) in SU(2) lattice gauge theory on 2 and 4 dimensiona
l lattices, both numerically and analytically. We consider five such a
lgorithms, and we measure four different observables. A detailed discu
ssion and analysis of the tuning of these algorithms is also presented
.