In TCBR, complexity refers to the extent to which similar problems have similar solutions. Casebase complexity measures proposed are based on the premise that a casebase is simple if similar problems have similar solutions. We observe, however, that such measures are vulnerable to choice of solution side representations, and hence may not be meaningful unless similarities between solution components of cases are shown to corroborate with human judgements. In this paper, we redefine the goal of complexity measurements and explore issues in estimating solution side similarities. A second limitation of earlier approaches is that they critically rely on the choice of one or more parameters. We present two parameter-free complexity measures, and propose a visualization scheme for casebase maintenance. Evaluation over diverse textual casebases show their superiority over earlier measures. © 2009 Springer Berlin Heidelberg.