We introduce an average case analysis of the search primitive operations (equality and thresholding) in associative memories. We provide a general framework for analysis, using as parameters the word space distribution and the CAM size parameters: m (number of memory words) and n (memory word length). Using this framework, we calculate the probability that the whole CAM memory responds to a search primitive operation after comparing up to k most significant bits (1 k n) in each word; furthermore, we provide a closed formula for the average value of k and the probability that there exists at least one memory word that equals the centrally broadcast word. Additionally, we derive results for the cases of uniform and exponential distribution of word spaces. We prove that in both cases the average value of k depends strongly on lg m, when n>lg m: for the case of uniform distribution, the average value is practically independent of n, while in the exponential depends weakly on the difference between the sample space size 2 n and the CAM size m. Furthermore, in both cases, the average k is approximately n when n lg m. Verification of our theoretical results through massive simulations on a parallel machine is presented. One of the main results of this work, that the average value of k can be much smaller than n article no.