From d21efa2beccedd16beeb653fbe20e70c156c0d96 Mon Sep 17 00:00:00 2001 From: mo khan Date: Sun, 7 Nov 2021 18:48:19 -0700 Subject: draw the recurrence tree --- 0x01/README.md | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) diff --git a/0x01/README.md b/0x01/README.md index e0a0016..a6ec5cc 100644 --- a/0x01/README.md +++ b/0x01/README.md @@ -384,6 +384,25 @@ properties. `T(n) = 4T(n/2) + cn` + 4T tells me that there are 4 sub problems. + The 4 sub problems can be broken down into sub problems and again and again + until the sub problems approach a base case. + + ```plaintext + n + | + ------------------------------ + / / \ \ + n/2 n/2 n/2 n/2 + / /\ \ + / / \ \ + n/4 n/4 n/4 n/4 + . + . + . + n/2^i + ``` + ```plaintext lg n T(n) = sigma 4i * c(n/2^i) -- cgit v1.2.3