循環参照検知：考察３

動くコードはできたが、このコードの計算量はいくらだろうか？

循環がない場合: m = 1 ですべてのノードの隣が検査されて終端を発見するため、計算量は n である。
循環が k 番目から (k - p) 番目に向けて発生している場合: m が p になるまでの計算量は (p-1)n であり、m = p における計算量は k であるから、全体の計算量は (p - 1)n + k になる。

ということは、O(n) である。

本当に？

HasLoop(node) の計算量は上記の通り O(n) だが、リンクリストに対する操作は HasLoop(node,int) で行われていて、その計算量は終端または引数の m である。よって、計算量は $\sum_{p=1}^m{m}=\frac{m(m+1)}2$ となるから、上記のコードは全体として $\large{o}(\frac{n^2}2)$ つまり $\large{O}(n^2)$ となる。ザンネーン。