Wie löst man eine Wiederholungsrelation wie $ T (n) = T (n/2) + T (n/4) + O (m) $

Question

Ich möchte die engere Grenze für diese Wiederholung erhalten, in der wir haben zwei Variablen m und n.

Wo

C so ist, dass n = C ist die Stopp-Bedingung:

Answer 1

Aus meiner vorherigen Antwort here, können wir eine binomischen Summen Formel für T(n) ableiten für T(n).

---

In Ihrem speziellen Beispiel sind die Konstanten: c1 = 1, c2 = 1, a = 2, b = 4, f(n) = O(m). Da O(m) keine Abhängigkeit von n hat, können wir einfach den f Begriff damit ersetzen.

Wie können wir die innere Summe zu bewerten? Denken Sie an die Binomialentwicklung für ganzzahlige Potenzen:

a = b = 1 Einstellung erhalten wir:

So: