= Solution
Interpret the source's $m$ as the maximum finite <shortest-path distance> among reachable pairs, taking $m=0$ when only length-zero <graph paths> are needed. This is the length bound required for <reflexive transitive closure>. A directed <graph cycle> permits arbitrarily long <walks>, so the maximum length of all possible <walks> would not be a finite termination parameter.<Functional programming, design and analysis of algorithms examination paper by the University of Oxford (2013)>[p. 6, Question 5(d), phrase “maximum path length in the transitive closure”]{ref}
For the elementary dense implementation, each <Boolean matrix multiplication> evaluates all $n^3$ triples $(i,t,j)$, with no early exit. Each equality test costs $O(n^2)$. Starting from $P_1$, the algorithm reaches $P_m$ after $m-1$ updates when $m\geq1$, then performs one further update to detect stability. Consequently, for $n\geq2$,
$$
\boxed{T_{\mathrm{extend}}=\Theta(n^3\max\{1,m\}),\qquad \text{auxiliary space}=\Theta(n^2).}
$$
For the usual nontrivial case $m\geq1$, this is $\Theta(mn^3)$. Since $m\leq n-1$, the overall worst case is $\Theta(n^4)$. This bound is tight for this implementation: the directed chain $0\to1\to\cdots\to n-1$ has $m=n-1$ and gains previously unknown pairs at every length until then, while every update scans all triples. This tightness does not claim an inherent lower bound for the <reflexive transitive closure> problem; it concerns the specified repeated-extension <algorithm>.
Back to article page
