algorithm - クイックソートでのパーティショニングのコスト

Question

クイックソートの分析における上記の関係(礼儀のsedgewickのアルゴリズム4)では、パーティショニングのコストは N+1 として与えられます。誰かがこれを説明できますか? これは N+1 比較ということですか?

（stackexchangeで同様の質問を試みましたが、役に立ちませんでした）

Answer 1

はい、平均して、パーティショニングには n+1 回の比較が必要です。(実際には n+1-(1/n))

http://users.encs.concordia.ca/~chvatal/notes/qs.pdf