time_complexity.md

PA-1 — Time Complexity Analysis (submission)

(ii) Compute the time complexity of Willans’ formula and compare it with the time complexity of your formula

Notation & facts used

• Let $p_n$ denote the $n$-th prime. By the Prime Number Theorem (using safe Rosser bounds):
  $$p_n = \Theta(n \log n).$$
• Although Willans-style formulas use a formal upper limit $N$ (e.g., $N = 2^n$), the summand becomes zero for $m \ge p_n$.
  Thus the effective limit is $m \approx p_n$.

---

1. Complexity of Willans’ original formula (Wilson / factorial detector)

What the detector does

• Willans uses Wilson’s theorem: $j$ is prime iff $(j-1)! + 1$ is divisible by $j$.
• Computing $(j-1)! \bmod j$ requires $\Theta(j)$ multiplications per $j$ on very large integers.

Naïve worst-case (formal limit $N = 2^n$)

$$ \sum_{m=1}^{2^n} \sum_{j=1}^{m} \Theta(j) = \sum_{m=1}^{2^n} \Theta(m^2) = \Theta((2^n)^3) = \Theta(2^{3n}). $$

This is exponential.

Practical (early stop at $m \approx p_n$)

$$ \sum_{m=1}^{p_n} \sum_{j=1}^{m} \Theta(j) = \sum_{m=1}^{p_n} \Theta(m^2) = \Theta(p_n^3). $$

Using $p_n = \Theta(n \log n)$:

$$ \boxed{\text{Willans (practical): } \Theta((n \log n)^3)}. $$

---

2. Complexity of Your modified formula (trial-division detector)

Detector cost

Your detector checks divisors up to $\sqrt{x}$:

$$T_{\text{detector}}(j) = \Theta(\sqrt{j}).$$

Cost to compute $\pi(m)$

$$ T_{\pi}(m) = \sum_{j=1}^{m} \Theta(\sqrt{j}) = \Theta(m^{3/2}). $$

Total cost (effective limit $m \approx p_n$)

$$ \sum_{m=1}^{p_n} \Theta(m^{3/2}) = \Theta(p_n^{5/2}). $$

Substitute $p_n$:

$$ \boxed{\text{Your method (practical): } O((n\log n)^{5/2})}. $$

Worst-theoretical (if forced to $2^n$)

$$ \sum_{m=1}^{2^n} \Theta(m^{3/2}) = \Theta((2^n)^{5/2}) = \Theta(2^{2.5n}). $$

---

3. Comparison & intuition

• Practical asymptotics:

  • Willans: $(n \log n)^3$
  • Your method: $(n \log n)^{5/2}$
    → Faster by about $(n \log n)^{1/2}$.

• Willans is much slower in practice because:

  • factorial values are enormous,
  • arithmetic operations are very expensive,
  • constants are huge.

---

4. Final Comparison Table

Method	Effective limit	Practical time (in $p_n$)	Time in $n$ (using $p_n \sim n\log n$)
Willans (factorial)	$m \le p_n$	$\Theta(p_n^3)$	$\Theta((n\log n)^3)$
Your method (trial division)	$m \le p_n$	$O(p_n^{5/2})$	$O((n\log n)^{5/2})$
Sieve of Eratosthenes	primes $\le p_n$	$O(p_n\log\log p_n)$	$O(n\log n\log\log(n\log n))$

---