  We consider the Complexity=Action (CA) proposal in Einstein gravity and
investigate new counterterms which are able to remove all the UV divergences of
holographic complexity. We first show that the two different methods for
regularizing the gravitational on-shell action proposed in Ref.
\cite{Carmi:2016wjl} are completely equivalent, provided that one considers the
Gibbons-Hawking-York term as well as new counterterms inspired from holographic
renormalization on timelike boundaries of the WDW patch. Next, we introduce new
counterterms on the null boundaries of the WDW patch for four and five
dimensional asymptotically AdS spacetimes which are able to remove all the UV
divergences of the on-shell action. Moreover, they are covariant and do not
change the equations of motion. At the end, by applying the null counterterms,
we calculate the holographic complexity of an AdS-Schwarzschild black hole as
well as the complexity of formation. We show that the null counterterms do not
change the complexity of formation.
