I introduce a measure of choice complexity based on the working memory load that a decision maker experiences as she sequentially processes information over multiple alternatives and attributes, in any order. The measure is analogous to the space complexity of an algorithm in computational complexity theory. I characterize the minimum complexity orders, formalizing the intuitions that «considering one alternative at a time» and considering attributes in a «systematic» way minimizes complexity. I then introduce a simple model of choice in which hazard (error) rates depend on complexity, and test it using the data from an existing experiment. The simplest one-parameter version of the model closely tracks a complicated pattern of choice errors across six treatments. In addition, I estimate the complexity-hazard rate curve, finding that it is increasing and roughly linear. Finally, I quantify the reduction in complexity and choice error rates offered by the well-known satisficing and elimination-by-aspects choice heuristics.