Educational researchers have been confronted with a multitude of definitions of task complexity and a lack of consensus on how to measure it. Using a cognitive load theory-based perspective, we argue that the task complexity that learners experience is based on element interactivity. Element interactivity can be determined by simultaneously considering the structure of the information being processed and the knowledge held in long-term memory of the person processing the information. Although the structure of information in a learning task can easily be quantified by counting the number of interacting information elements, knowledge held in long-term memory can only be estimated using teacher judgment or knowledge tests. In this paper, we describe the different perspectives on task complexity and present some concrete examples from cognitive load research on how to estimate the levels of element interactivity determining intrinsic and extraneous cognitive load. The theoretical and practical implications of the cognitive load perspective of task complexity for instructional design are discussed.