diff options
| -rw-r--r-- | 0x01/README.md | 48 |
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) + ``` |