Summary: We prove that the height of any algebraic computation tree for deciding membership in a semialgebraic set \(\Sigma \subset {\mathbb R}^n\) is bounded from below by \[ \frac{c_1\log (\mathrm{b}_m(\Sigma))}{m+1} -c_2n, \] where \(\mathrm{b}_m(\Sigma)\) is the \(m\)th Betti number of \(\Sigma \) with respect to “ordinary” (singular) homology and \(c_1\), \(c_2\) are some (absolute) positive constants. This result complements the well-known lower bound by A. C. C. Yao [J. Comput. Syst. Sci. 55, No. 1, 36–43 (1997; Zbl 0880.68100)] for locally closed semialgebraic sets in terms of the total Borel-Moore Betti number. We also prove that if \(\rho : {\mathbb R}^n \rightarrow {\mathbb R}^{n-r}\) is the projection map, then the height of any tree deciding membership in \(\Sigma \) is bounded from below by \[ \frac{c_1\log (\mathrm{b}_m(\rho (\Sigma)))}{(m+1)^2} -\frac{c_2n}{m+1} \] for some positive constants \(c_1\), \(c_2\). We illustrate these general results by examples of lower complexity bounds for some specific computational problems.