Periodic bottlenecks in population sizes are common in natural (e.g., host-to-host transfer of pathogens) and laboratory populations of asexual microbes (e.g., experimental evolution) and play a major role in shaping the adaptive dynamics in such systems. Existing theory predicts that for any given bottleneck size (N0) and number of generations between bottlenecks (g), populations with similar harmonic mean size (HM=N0g)) will have similar extent of adaptation (EoA). We test this widely cited claim using long-term evolution in Escherichia coli populations and computer simulations. We show that, contrary to the predictions of the extant theory, HM fails to predict and explain EoA. Although larger values of g allow populations to arrive at superior benefits by entailing increased number of individuals, they also lead to lower EoA. We also show analytically how the extant theory overestimates the effective population size relevant for adaptation. Altering the current theory using these insights, we propose and demonstrate that N0/g (and not N0g) successfully predicts EoA. Our results call for a re-evaluation of the role of population size in two decades of microbial population genetics and experimental evolution studies. These results are also helpful in predicting microbial adaptation, which has important evolutionary, epidemiological and economic implications.