は再発関係T（N）= T（N-√N）+1

Question

私は分裂を学習し、コーセラにおけるアルゴリズムを征服していますが、私はこの再発関係に遭遇した解法ある与えられた：

O(√n)

私は、マスターメソッドと再発ツリー分析を学んだが、私は、この再発の関係を分析する方法がわかりません。
ご協力いただきありがとうございます。 RHSたびつまり、大n用LHSよりも小さいことが

注：我々は、二項展開を使用して、この段階での上限を得ることができる

Answer 1

我々は近似を適用して、より小さな値をパラメータから引いてTにし、結果は上限になります。 mの反復に続き

：T(n)はn = 0で終了すると仮定すると

（またはいくつかの定数、重要ではありません）

ため、複雑さがO(m) = O(√n)です。

---

EDIT：上記= 4√nが間違っていた、申し訳ありません - あなたはこれまでに試してみました何(2+5/√2)√n