This paper presents measures for upper and lower bounding the instance- based complexity of AND/OR search algorithms for solution counting and related #P problems. This can be of utmost importance in selecting the right set of pa- rameters for fitting an algorithm to a problem instance and in devising heuristics during execution. To this end we estimate the size of the search space, with spe- cial consideration given to the impact of determinism in a problem. The resulting schemes are evaluated empirically on a variety of problem instances; in many cases relatively tight bounds are obtained, far better than those implied by the tree width or hypertree width. Specific results are provided detailing how these measures can be useful for discriminating between variable orderings.