  We study the action growth rate in the Wheeler-DeWitt (WDW) patch for a
variety of $D\ge 4$ black holes in Einstein gravity that are asymptotic to the
anti-de Sitter spacetime, with spherical, toric and hyperbolic horizons,
corresponding to the topological parameter $k=1,0,-1$ respectively. We find a
lower bound inequality $\frac{1}{T} \frac{\partial \dot I_{\rm WDW}}{\partial
S}|_{Q,P_{\rm th}}> C$ for $k=0,1$, where $C$ is some order-one numerical
constant. The lowest number in our examples is $C=(D-3)/(D-2)$. We also find
that the quantity $(\dot I_{\rm WDW}-2P_{\rm th}\, \Delta V_{\rm th})$ is
greater than, equal to, or less than zero, for $k=1,0,-1$ respectively. For
black holes with two horizons, $\Delta V_{\rm th}=V_{\rm th}^+-V_{\rm th}^-$,
i.e. the difference between the thermodynamical volumes of the outer and inner
horizons. For black holes with only one horizon, we introduce a new concept of
the volume $V_{\rm th}^0$ of the black hole singularity, and define $\Delta
V_{\rm th}=V_{\rm th}^+-V_{\rm th}^0$. The volume $V_{\rm th}^0$ vanishes for
the Schwarzschild black hole, but in general it can be positive, negative or
even divergent. For black holes with single horizon, we find a relation between
$\dot I_{\rm WDW}$ and $V_{\rm th}^0$, which implies that the holographic
complexity preserves the Lloyd's bound for positive or vanishing $V_{\rm
th}^0$, but the bound is violated when $V_{\rm th}^0$ becomes negative. We also
find explicit black hole examples where $V_{\rm th}^0$ and hence $\dot I_{\rm
WDW}$ are divergent.
