CS Unplugged: Field guide: Complexity and tractability

An online resource for teaching Computer Science to students, this chapter focusses on complexity and tractability. This chapter covers problems where it's easy to tell the computer what to do --- by writing a program --- but the computer can’t do what we want because it takes far too long. Find out about what is meant by tractable and an intractable problem. Learn about complexity, why its an important concept and how it relates to algorithms.

Additional details

Year band(s) 7-8, 9-10
Format Web page
Core and overarching concepts Algorithms
Australian Curriculum Digital Technologies code(s)

Design algorithms involving nested control structures and represent them using flowcharts and pseudocode


Trace algorithms to predict output for a given input and to identify errors


Evaluate existing and student solutions against the design criteria, user stories and possible future impact


Design algorithms involving logical operators and represent them as flowcharts and pseudocode


Validate algorithms and programs by comparing their output against a range of test cases


Implement, modify and debug modular programs, applying selected algorithms and data structures, including in an object-oriented programming language

Keywords Tractable, Intractable, Algorithms, Sorting, Searching, Complexity

University of Canterbury, New Zealand


University of Canterbury, New Zealand. Creative Commons BY-NC-SA 4.0.