Measuring and Classifying Complexity is an important topic in the last unit of Theory of Computation. It deals with determining how much time and memory a computational problem requires.
An algorithm may be solvable, but it may require too much time or memory. Complexity theory helps us study this issue.
Computability asks: “Can we solve the problem?”
Complexity asks: “How efficiently can we solve it?”
1. What is Computational Complexity?
Computational complexity is the study of the resources required by an algorithm or Turing Machine to solve a problem.
The two most important resources are:
- Time Complexity – How many computational steps are required?
- Space Complexity – How much memory/tape space is required?
2. Time Complexity
Time complexity measures the number of steps performed by an algorithm as a function of the input size.
If the input size is \(n\), we express the running time as:\[ T(n) \]
Example
Suppose an algorithm examines every element of an array once.
For:\[ n=10 \]
approximately 10 operations are performed.
For:\[ n=1000 \]
approximately 1000 operations are performed.
Therefore:\[ T(n)=O(n) \]
This is called linear time complexity.
3. Space Complexity
Space complexity measures the amount of memory required by an algorithm as a function of input size.
It is represented by:\[ S(n) \]
For example, if an algorithm needs an additional array of size \(n\):\[ S(n)=O(n) \]
Therefore:
- Time → Number of computational steps
- Space → Amount of memory used
4. Input Size
Complexity is normally expressed in terms of input size \(n\).
For example:
If an algorithm receives a string:
101101001
then:\[ n=9 \]
If it receives a graph with \(n\) vertices, complexity may be expressed in terms of the number of vertices and edges.
The important idea is:
As input size increases, how does the required computational resource increase?
5. Asymptotic Notation
Complexity is commonly described using asymptotic notation.
The most important notation is:
Big-O — \(O\)
It gives an upper bound on growth.
For example:\[ T(n)=O(n^2) \]
means the running time grows no faster than a constant multiple of \(n^2\), asymptotically.
Big-Omega — \(\Omega\)
It gives a lower bound.\[ T(n)=\Omega(n) \]
means the algorithm requires at least proportional-to-\(n\) work asymptotically.
Big-Theta — \(\Theta\)
It gives a tight asymptotic bound.\[ T(n)=\Theta(n) \]
means the running time grows proportionally to \(n\), up to constant factors.
6. Common Complexity Classes
Some common growth rates are:
| Complexity | Name | Example idea |
|---|---|---|
| \(O(1)\) | Constant | Accessing an array element |
| \(O(\log n)\) | Logarithmic | Binary search |
| \(O(n)\) | Linear | Sequential search |
| \(O(n\log n)\) | Linearithmic | Efficient sorting |
| \(O(n^2)\) | Quadratic | Simple nested loops |
| \(O(n^3)\) | Cubic | Some matrix algorithms |
| \(O(2^n)\) | Exponential | Many brute-force algorithms |
| \(O(n!)\) | Factorial | Many permutation-based searches |
7. Growth Comparison
Consider increasing input size:
O(1)
↓
O(log n)
↓
O(n)
↓
O(n log n)
↓
O(n²)
↓
O(n³)
↓
O(2ⁿ)
↓
O(n!)
Generally, the lower growth rates are more desirable for large inputs.
Memory Trick
Constant → Log → Linear → N Log N → Quadratic → Exponential → Factorial
8. Complexity Classes
Complexity theory classifies computational problems into classes based on the resources required to solve them.
Important classes include:
- P
- NP
- NP-Hard
- NP-Complete
These are particularly important when discussing tractable and intractable problems.
9. Class P
P stands for Polynomial Time.
It contains decision problems that can be solved by a deterministic algorithm in polynomial time.
Examples of polynomial forms include:\[ O(n) \]\[ O(n^2) \]\[ O(n^3) \]\[ O(n^k) \]
where \(k\) is a constant.
Examples
- Sorting
- Searching
- Shortest-path problems
- Minimum spanning tree
The exact complexity depends on the algorithm and problem formulation.
Simple idea:
P = Problems that can be solved efficiently (in polynomial time).
10. Class NP
NP stands for Nondeterministic Polynomial Time.
It consists of decision problems for which a proposed solution can be verified in polynomial time by a deterministic algorithm.
For example, consider a problem asking:
Does this graph contain a Hamiltonian cycle?
If someone gives us a proposed cycle, we can check in polynomial time whether it is a valid Hamiltonian cycle.
Therefore, the problem belongs to NP.
Simple idea:
NP = A given solution can be verified efficiently.
11. Relationship Between P and NP
Every problem in P is also in NP:\[ \boxed{P\subseteq NP} \]
because if we can solve a problem efficiently, we can certainly verify its solution efficiently.
The famous question is:\[ \boxed{P=NP\ ?} \]
It is still an open problem.
12. NP-Complete Problems
An NP-Complete problem has two properties:
- It belongs to NP.
- Every problem in NP can be reduced to it in polynomial time.
Examples include:
- SAT
- 3-SAT
- Traveling Salesperson Problem (decision version)
- Clique
- Vertex Cover
- Hamiltonian Cycle
Important Point
If any one NP-Complete problem can be solved in polynomial time, then:\[ P=NP \]
13. NP-Hard Problems
A problem is NP-Hard if it is at least as hard as every problem in NP, under the relevant polynomial-time reductions.
An NP-Hard problem does not necessarily have to belong to NP.
For example, some optimization problems are NP-Hard without being decision problems in NP.
Relationship:
NP-Hard
┌───────────────┐
│ │
│ NP-Complete │
│ ┌────┐ │
│ │ NP │ │
│ └────┘ │
└───────────────┘
More precisely:\[ \boxed{NP\text{-Complete}=NP\cap NP\text{-Hard}} \]
14. Tractable and Intractable Problems
This is the next topic in your syllabus.
Tractable
A problem is generally called tractable if it can be solved efficiently, typically in polynomial time.
Examples:\[ O(n),\ O(n^2),\ O(n^3) \]
Intractable
A problem is generally considered intractable when no polynomial-time algorithm is known and the problem is believed to require super-polynomial/exponential time in general.
Examples often include:\[ O(2^n) \]
or\[ O(n!) \]
for straightforward algorithms.
Important: Intractable does not mean unsolvable.
15. Unsolvable vs Intractable
This is extremely important for the examination.
| Unsolvable | Intractable |
|---|---|
| No algorithm exists | An algorithm exists |
| Cannot be solved for all inputs | Can be solved |
| Fundamental computability limitation | Efficiency limitation |
| Example: Halting Problem | Example: many NP-Hard problems |
| No guaranteed decider | A decider may exist |
Remember:
Unsolvable = Cannot compute.
Intractable = Can compute, but may be too expensive.
16. Measuring Complexity Using Turing Machines
In Theory of Computation, complexity can also be measured using Turing Machines.
Time Complexity
Count the number of transitions made by the TM before it halts.\[ T(n)=\text{maximum number of steps for input size }n \]
Space Complexity
Count the amount of tape used during computation.\[ S(n)=\text{maximum tape cells used for input size }n \]
Thus:
Turing Machine
↓
┌────┴────┐
↓ ↓
Time Space
↓ ↓
Steps Tape cells
17. Why Do We Measure Complexity?
Complexity analysis helps us:
- Compare algorithms.
- Select efficient algorithms.
- Estimate performance for large inputs.
- Understand computational limitations.
- Classify problems.
- Determine whether a problem is practically feasible.
- Study the difference between efficient and inefficient computation.
18. Complete Concept Map
Computational Problems
↓
Can it be solved?
/ \
Yes No
↓ ↓
Computable Unsolvable
↓
How efficiently?
↓
Complexity
↓
┌───────┴────────┐
↓ ↓
Time Space
↓ ↓
T(n) S(n)
↓
Complexity Classes
↓
┌──┴───────────────┐
P NP NP-Hard
└── NP-Complete
5–10 Marks Exam Answer
Measuring and Classifying Complexity
Computational complexity is the study of the resources required by an algorithm or Turing Machine to solve a problem. The two major resources are time and space.
Time complexity measures the number of computational steps required as a function of input size \(n\), represented by \(T(n)\). Space complexity measures the amount of memory or tape space required, represented by \(S(n)\).
Complexity is commonly expressed using asymptotic notations such as:
- \(O\) — upper bound
- \(\Omega\) — lower bound
- \(\Theta\) — tight bound
Common complexity classes include:\[ O(1),\ O(\log n),\ O(n),\ O(n\log n),\ O(n^2),\ O(2^n),\ O(n!) \]
Problems are also classified into important complexity classes such as P, NP, NP-Hard and NP-Complete.
- P: Problems solvable in polynomial time.
- NP: Problems whose proposed solutions can be verified in polynomial time.
- NP-Hard: Problems at least as hard as every problem in NP.
- NP-Complete: Problems that are both NP and NP-Hard.
The important relationship is:\[ \boxed{P\subseteq NP} \]
The question of whether:\[ P=NP \]
is a major unsolved problem in computer science.
Fast Memory Trick
Complexity = Time + Space
Notation = \(O,\Omega,\Theta\)
Main classes = P, NP, NP-Hard, NP-Complete
And remember the most important distinction:
Unsolvable → No algorithm
Intractable → Algorithm exists, but may require excessive resources
