  We investigate the holographic complexity of CFTs compactified on a circle
with a Wilson line, dual to magnetized solitons in AdS$_4$ and AdS$_5$. These
theories have a confinement-deconfinement phase transition as a function of the
Wilson line, and the complexity of formation acts as an order parameter for
this transition. Through explicit calculation, we show that proposed complexity
functionals based on volume and action obey a scaling relation with radius of
the circle and further prove that a broad family of potential complexity
functionals obeys this scaling behavior. As a result, we conjecture that the
scaling law applies to the complexity of conformal field theories on a circle
in more general circumstances.
