Complexity Theory

Overview

Complexity theory focuses on whether problems are easy or hard. Where computability theory asks if a language is decidable, complexity theory asks whether a language is decidable given some restriction on the resources.

A problem is intractable if such a problem is solvable in principle but with solutions requiring so much time or space that they can't be used in practice.

Order of Growth

An algorithm's order of growth refers to how the amount of resources an algorithm requires changes as its input size increases. Usually running time and space usage are studied.