To function in a complex world, our brains must somehow stream our experiences into memory in real time as they occur. An “online” memory of this kind must form durable memory traces based on a single exposure to each incoming pattern, while preserving older experiences as long as possible. Using computer models and mathematical analysis, we studied the online learning capabilities of a biologically inspired memory, with the goal to understand how the properties of neurons, dendrites, and synapses interact to determine online storage capacity. A key assumption was that dendrites, rather than whole neurons, are the main representational units used to encode learned information. In previous work (Wu and Mel, 2009), we focused on synaptic plasticity rules and their impact on online storage capacity. In this work, given that learning operates at the level of dendrites, we set out to identify the factors that determine optimal dendrite “size” (i.e. the number of synapses on each dendrite). We show that capacity is maximized when dendrites are of “medium” size, that is, when each dendrite contains a few hundred synapses rather than 10’s or 1000’s of synapses. We show why both short and long dendrites suffer from severe capacity costs: long dendrites lead to wasteful over-representation, while short dendrites suffer from greater susceptibility to noise as well as a previously undescribed problem of “dendrite availability”. We also studied the relationship between optimal dendrite size and properties of the input patterns: increased pattern density and noise both reduced capacity, but denser patterns push for shorter dendrites while noisier patterns push for longer dendrites. Our results can help clarify which morphological changes that occur with aging, stress, neurological disorders, and mental retardation are likely to be most detrimental to online recognition memory, and why.