---
title: "Define computational complexity"
subject: "Theory of Computation"
chapter: 6
key: "semester_3/theory_of_computation:computational-complexity-define"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/computational-complexity-define
site: BCT Engineering
---

# Define computational complexity

Theory of Computation · Chapter 6: Computational Complexity

- Asked in: 2072 Chaitra; 2073 Chaitra (asked 2 times)
- Video: [What is Complexity Theory?](https://www.youtube.com/watch?v=r49Yqtrx1tU) — Easy Theory
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/computational-complexity-define
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-6

## Question

Define computational complexity. (Write a short note on computational complexities.)

## Short answer

Computational complexity studies the time and space resources an algorithm needs as a function of input size n. Time complexity T(n) is the max steps; space complexity S(n) is max tape cells. It classifies problems into classes like P (polynomial time), NP, PSPACE, EXPTIME. Complexity separates tractable problems (in P) from intractable ones.

## Answer

**Computational complexity** is the study of the **resources** (mostly time and memory space) that an algorithm or Turing machine needs to solve a problem, as a function of the input size n. It classifies problems by how hard they are to solve, not just by whether they are solvable.

#### Measures
- **Time complexity T(n):** the maximum number of steps (moves) a TM takes on any input of length n.
- **Space complexity S(n):** the maximum number of tape cells the TM uses on any input of length n.

Complexities are expressed in asymptotic notation, such as O(n), O(n²) and O(2ⁿ), and are usually studied for the worst case.

#### Complexity classes
| Class | Meaning |
|---|---|
| P | solvable by a deterministic TM in polynomial time, O(nᵏ) |
| NP | solvable by a non-deterministic TM in polynomial time (a solution can be **verified** in polynomial time) |
| PSPACE | solvable using polynomial space |
| EXPTIME | solvable by a deterministic TM in time $2^{p(n)}$ for some polynomial p |

Known: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME. Whether P = NP is an open problem.

#### Importance
Problems in P are called **tractable** (practical); problems that need exponential time are **intractable** for large n (for example the travelling salesman problem, as far as we know). Examples: sorting is O(n log n) (in P); SAT is in NP and is NP-complete.

Complexity theory separates problems that are merely hard from those that are undecidable, and it guides the choice between exact, approximate and heuristic algorithms.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does computational complexity study?
   A. Only whether a problem is solvable or not
   B. The resources (time and space) needed to solve a problem as a function of input size n
   C. The number of lines in an algorithm's code
   D. The hardware speed needed to run a program
   Answer: B. Complexity measures resources such as time and memory as functions of n, and classifies problems by how hard they are, not just whether they are solvable. (Key point: Definition)

2. How are T(n) and S(n) defined for a Turing machine?
   A. T(n) is the average number of steps, S(n) the number of states
   B. T(n) is the number of states, S(n) the number of symbols
   C. T(n) is the minimum steps, S(n) the minimum cells used
   D. T(n) is the maximum number of steps and S(n) the maximum number of tape cells used on any input of length n
   Answer: D. Both are worst-case measures over all inputs of length n. (Key point: Time and space measures)

3. Which statement about P and NP is correct?
   A. P is solved by a deterministic TM in polynomial time; NP by a non-deterministic TM in polynomial time (answers verifiable in polynomial time)
   B. P needs exponential time; NP needs polynomial space
   C. NP is solved by a deterministic TM in exponential time only
   D. P and NP are proven to be equal
   Answer: A. P uses a deterministic TM in polynomial time, NP a non-deterministic one; P = NP is an open problem. (Key point: Classes P and NP)

4. Which pairing of class inclusions and meaning is correct?
   A. EXPTIME is inside P, and P problems are intractable
   B. P is inside NP, which is inside PSPACE, which is inside EXPTIME; problems in P are called tractable
   C. NP is inside P, and exponential-time problems are tractable
   D. PSPACE is inside P, and sorting is intractable
   Answer: B. The known chain is P ⊆ NP ⊆ PSPACE ⊆ EXPTIME. Polynomial-time problems are tractable, while exponential ones are intractable for large n. (Key point: Tractable vs intractable)