https://ideone.com/qPsn3a

5年前のメモです
証明が非常に簡略化して書いてあります
(書いた本人でも解読に時間がかかる)
またコードにコメントで計算量が書いてあります
参考にしてください