TM running-time profiler · empirical n vs steps

Theoretical analysis predicts O(n²) for the {0ⁿ1ⁿ} single-tape decider. Empirical: plot actual step counts. The data points should lie on or under a parabola.

• Empirical data only suggests, never proves. A clean quadratic fit through a dozen data points is consistent with O(n²) but doesn't prove it — a hidden log factor or constant could be invisible at small n.
• Look at steps/n², not just steps. If steps/n² approaches a constant as n grows, you have Θ(n²). If it grows, the actual complexity is higher.
• Watch for outliers and pessimistic-vs-best-case inputs. The same TM may take wildly different time on different inputs of the same length. Profile worst-case examples, not average.

• Q1. How does empirical data confirm an O(n²) bound?
  Doubling n should approximately quadruple the step count. Plotting steps / n² against n should give a roughly flat line. If the ratio drifts upward, hidden log factors are present.
• Q2. Could there be a constant factor we miss?
  Yes — Big-O ignores constants. Empirical timing can't reveal asymptotic equivalence vs huge multiplicative constants. But the shape (linearity of steps/n²) is the asymptotic claim and is what we test.
• Q3. What would fail this empirical check?
  If the algorithm secretly took O(n²·log n), you'd see slight upward curvature in steps/n² as n grows. If it were O(n³), steps/n² would grow linearly. If it were O(n log n), steps/n² would decrease.
• Q4. What's the relationship between this and the actual proof?
  Empirical profiling is sanity-checking, not proof. A formal Θ(n²) proof requires both an upper bound (here, n/2 pairs × O(n) per pair) and a lower bound (the crossing-sequence argument). Empirics validate the upper bound; the lower bound requires combinatorial analysis.

Sipser: Example 7.2. Lecture notes: Module 4 slide 3. Companion problems: P17 (growth race), P18 (single-tape 0ⁿ1ⁿ), P19 (two-tape race).