Time Complexity

YouTube

$A=\{a^k{b}^k|k\ge 0\}$

• 1-tape TM: O(n log n)
• Multi-tape TM: O(n)

Computability Theory: model independence Complexity Theory: model dependence

TIME Complexity Class

All reasonable deterministic models are polynomially related.

The Class P

Defn: $P={\bigcup }_{k}TIME(n^k)$ = Polynomial time decidable language

• Invariant for all reasonable deterministic models

$PATH\in P$

Polynomial Time: Each stage is polynomial and the total number of steps polynomial

The Class NP