learn the master method

1 files changed, 48 insertions, 0 deletions

diff --git a/0x01/README.md b/0x01/README.md
index ec5a526..47bc84b 100644
--- a/0x01/README.md
+++ b/0x01/README.md
@@ -382,8 +382,56 @@ properties.
   and provide a tight asymptotic bound on its solution. Verify your bound by the
   substitution method.
 
+  `T(n) = 4T(n/2) + cn`
+
+  ```plaintext
+         lg n
+  T(n) = sigma  4i * c(n/2^i)
+         i = 0
+
+              lg n
+       = cn * sigma 2^i
+              i=0
+
+       = cn * (2^(lg n+1) - 1) / (2 - 1)
+
+       = cn * (2*2^(lg n) - 1)
+
+       = cn * (2n - 1)
+
+       = 2cn^2 - cn
+  ```
+
+  Upper bound
+
+  ```plaintext
+  T(n) = 2cn^2 - cn
+       <= 2cn^2
+       = O(n^2)
+  ```
+
+  Lower bound
+
+  ```plaintext
+  T(n) = 2cn^2 - cn
+       = cn^2 + (cn^2 - cn)
+       >= cn^2
+       = sigma(n^2)
+  ```
+
 1. Exercise 4.5-3 from the textbook (10 marks)
 
   Use the master method to show that the solution to the binary-search
   recurrence `T(n) = T(n/2) + theta(1)` is `T(n) = theta(lg n)`. (See Exercise
   2.3-5 for a description of binary search.)
+
+  The master method is `T(n) = aT(n/b) + f(n)` where `a >= 1` and `b > 1`.
+
+  ```plaintext
+  T(n) = aT(n/b) + f(n)
+  T(n) = 1T(n/2) + f(n)
+  a = 1, b = 2
+
+  f(n) = theta(n^(lg 1)) = theta(1)
+  T(n) = theta(lg n)
+  ```