Great question! This is a really practical problem when dealing with algorithms that have factorial/exponential time complexity—where even small input sizes can lead to massive runtimes, and you need to tell the difference between "just taking a long time" and "actually stuck in an infinite loop." Let's break this down step by step.

Core Idea #

The key insight is to compare the actual runtime against a theoretical upper bound of normal completion time. As the actual runtime exceeds this bound, the probability that the algorithm is non-terminating should increase smoothly from 0 to 1, and be monotonically increasing.

Step 1: Define a Benchmark Runtime #

First, we need to translate the asymptotic complexity Q (e.g., O(N!)) into a concrete, practical upper bound for a normal run. Let's define:

T_bench = C * P * g(N)

Where:

• P: Constant time per individual operation (e.g., 0.5s per permutation)
• g(N): The concrete function from your complexity class Q (e.g., g(N) = N! for O(N!))
• C: A calibration constant (typically between 1.5–5) to account for real-world overheads like system scheduling, cache misses, or minor algorithmic inefficiencies. You can calibrate C by running small test cases and measuring the ratio of actual maximum runtime to P*g(N).

Probability Function Options #

Below are two robust, easy-to-implement functions that meet your requirements:

Option 1: Exponential Cumulative Distribution #

This function has a sharp rise after exceeding T_bench, which is great for cases where you want to quickly gain confidence in a non-termination:

f(t, P, N, Q) = 1 - exp( - (t / T_bench) ^ α )

Where:

• t: Current runtime of the algorithm
• α: Shape parameter (1.5–3 works well; higher values make the function rise faster after T_bench)

Behavior:

• When t = 0, f = 0 (no chance of non-termination at startup)
• When t = T_bench, f ≈ 0.63 (63% probability of non-termination)
• When t = 2*T_bench and α=2, f ≈ 0.98 (98% probability)
• As t → ∞, f → 1 (asymptotically approaches certainty)

Option 2: Logistic (Sigmoid) Function #

This function has a smooth S-shaped curve, which is more conservative and ideal for cases where you want to avoid false positives:

f(t, P, N, Q) = 1 / ( 1 + exp( -k*(t - T_bench) ) )

Where:

• k: Slope parameter (try k = 0.5 / T_bench to center the steepest rise at T_bench)

Behavior:

• When t = T_bench, f = 0.5 (50/50 chance of non-termination)
• When t is far below T_bench, f ≈ 0
• When t is far above T_bench, f ≈ 1
• The curve rises smoothly, making it easier to tune for gradual confidence building

Addressing Limitations & Improving Reliability #

These functions work well, but they have edge cases. Here's how to make them more robust:

• Calibrate C Dynamically: Instead of hardcoding C, run small test cases (e.g., N=1,2,...,5 for permutations) and fit a linear model to the actual runtime data. This gives you a data-driven C_actual that accounts for your specific environment and algorithm quirks.
• Add Progress Monitoring: If your algorithm can output intermediate progress (e.g., "generated 10,000 permutations so far"), calculate the expected remaining runtime as (t * total_work) / completed_work. If this expected time is way larger than T_bench, boost the non-termination probability.
• Combine with System Metrics: Don't rely solely on runtime—check if CPU usage is stuck at 100% (common for infinite loops) or memory usage is continuously growing (sign of a leak). If both metrics are abnormal alongside exceeding T_bench, increase your confidence in non-termination.
• Set a Confidence Threshold: Pick a threshold (e.g., f >= 0.99) and terminate the algorithm once this threshold is crossed. This gives you a clear, actionable rule for deciding when to stop waiting.

Example Calculation #

For your permutation example:

• P=0.5s, N=8, g(N)=8!=40320, C=1.2
• T_bench = 1.2 * 0.5 * 40320 = 24192s (~6.7 hours)
• Using Option 1 with α=2:
  • At t=20160s (theoretical runtime), f ≈ 0.5
  • At t=24192s, f ≈ 0.63
  • At t=48384s (2x T_bench), f ≈ 0.98—this is a good point to terminate and flag the algorithm as non-terminating.

内容的提问来源于stack exchange，提问作者TimzyPatzy