Finally, something apt for my appetite!
4-3[clrs]:
Since I'm a lazy person, I'll not show the lower bounds.
For the upper bound:
First of all we'll need two summations:
$$\sum_{j=0}^{j=i}(\frac {4}{3})^j = 4[(\frac{4}{3})^i-1]$$
and
$$\sum_{j=0}^{j=i}(j \times (\frac {4}{3})^j) = M = 1 \times (4/3)+2 \times (4/3)^2+ 3 \times (4/3)^3 +...+i \times (4/3)^i \\ \frac {4}{3} \times M = 1 \times (4/3)^2 + 2 \times (4/3)^3 + 3 \times (4/3)^4 +...+i \times (4/3)^{i+1} \\ M - \frac{4}{3} \times M = \sum_{j=1}^{j=i}(\frac{4}{3})^j-i \times (\frac{4}{3})^{i+1}\\ \frac{M}{3} = i \times (\frac{4}{3})^{i+1}-4 \times (\frac {4}{3})^i+4 \\ M = 3i \times (\frac{4}{3})^{i+1}-12 \times(\frac{4}{3})^i+12 \\ = (4i-12) \times (\frac{4}{3})^i+12$$
Now, see $$T(n) = 4 T(\frac{4}{3})+nlgn \\ = 4 ( 4T(n/3^2)+(n/3)lg(n/3))+nlgn \\ = 4 ^2 T(n/3^2)+(4/3)lg(n/3)+n lgn \\ = 4 ^3 T(n/3^3)+ (4/3)^2lg(n/3^2)+n lgn \\ = 4^i T(n/3^i)+ \sum_{j=1}^{j=i}(\frac{4}{3})^{j-1}lg(\frac{n}{3^{j-1}}) \\ = 4^iT(n/3^i)+ \frac{3}{4} \times \sum_{j=1}^{j=i} (\frac{4}{3})^j[lgn - (j-1)lg3] \\ = 4^i T(n/3^i)+ \frac{3}{4} \times lgn \times \sum_{j=1}^{j=i} (\frac{4}{3})^j - \frac{3}{4} log 3 \sum_{j=1}^{j=i} j \times (\frac{4}{3})^j + \frac{3}{4} lg3 \times \sum_{j=1}^{j=i} (\frac{4}{3})^j \\ = 4^i T(n/3^i)+3\times lgn [4 [(\frac{4}{3})^i-1]] -\frac{3}{4} log 3 [(4i-12)(\frac{4}{3})^i+12]+\frac{3}{4}\times lg3 [4[(\frac{4}{3})^i-1]] \\ = 4^iT(n/3^i)+3\times lgn \times (\frac{4}{3})^i -3\times lg 4 - 3 \times lg3 [ 4i\times (4/3)^i-12 (4/3)^i+12]+3 lg3 \times (4/3)^i- \frac{3}{4}lg3 $$
Since, we're finding only the asymptotic bounds, therefore, we can remove the constant terms, and moreover $n/3^i=1$ when $i=log_3n = k$. Therefore, doing that:
$$T(n) = 4^k \times T(1) + 3 lgn \times (\frac{4}{3})^k - 4k (4/3)^k +12\times /3)^k -12 +(4/3)^k \\= 4^{log_3n} + 3 log_2n \frac{4^{log_3n}}{n}-\frac{4 log_3n}{n}+\frac{4^{log_3n}}{n}-12$$
From this equation, we can see that the largest term is $4^{log_3n}$. Hence the asymptotic upperbound of the given recurrence is $O(4^{log_3n})=O(n^{log_34})$.
4-3[clrs]:
Give asymptotic upper and lower bounds for $T(n)$ in each of the following recurrences. Assume that $T(n)$ is constant for sufficiently small $n$. Make your bounds as tight as possible, and justify your answers.(a) $T(n) = 4T(n/3)+nlgn$
Since I'm a lazy person, I'll not show the lower bounds.
For the upper bound:
First of all we'll need two summations:
$$\sum_{j=0}^{j=i}(\frac {4}{3})^j = 4[(\frac{4}{3})^i-1]$$
and
$$\sum_{j=0}^{j=i}(j \times (\frac {4}{3})^j) = M = 1 \times (4/3)+2 \times (4/3)^2+ 3 \times (4/3)^3 +...+i \times (4/3)^i \\ \frac {4}{3} \times M = 1 \times (4/3)^2 + 2 \times (4/3)^3 + 3 \times (4/3)^4 +...+i \times (4/3)^{i+1} \\ M - \frac{4}{3} \times M = \sum_{j=1}^{j=i}(\frac{4}{3})^j-i \times (\frac{4}{3})^{i+1}\\ \frac{M}{3} = i \times (\frac{4}{3})^{i+1}-4 \times (\frac {4}{3})^i+4 \\ M = 3i \times (\frac{4}{3})^{i+1}-12 \times(\frac{4}{3})^i+12 \\ = (4i-12) \times (\frac{4}{3})^i+12$$
Now, see $$T(n) = 4 T(\frac{4}{3})+nlgn \\ = 4 ( 4T(n/3^2)+(n/3)lg(n/3))+nlgn \\ = 4 ^2 T(n/3^2)+(4/3)lg(n/3)+n lgn \\ = 4 ^3 T(n/3^3)+ (4/3)^2lg(n/3^2)+n lgn \\ = 4^i T(n/3^i)+ \sum_{j=1}^{j=i}(\frac{4}{3})^{j-1}lg(\frac{n}{3^{j-1}}) \\ = 4^iT(n/3^i)+ \frac{3}{4} \times \sum_{j=1}^{j=i} (\frac{4}{3})^j[lgn - (j-1)lg3] \\ = 4^i T(n/3^i)+ \frac{3}{4} \times lgn \times \sum_{j=1}^{j=i} (\frac{4}{3})^j - \frac{3}{4} log 3 \sum_{j=1}^{j=i} j \times (\frac{4}{3})^j + \frac{3}{4} lg3 \times \sum_{j=1}^{j=i} (\frac{4}{3})^j \\ = 4^i T(n/3^i)+3\times lgn [4 [(\frac{4}{3})^i-1]] -\frac{3}{4} log 3 [(4i-12)(\frac{4}{3})^i+12]+\frac{3}{4}\times lg3 [4[(\frac{4}{3})^i-1]] \\ = 4^iT(n/3^i)+3\times lgn \times (\frac{4}{3})^i -3\times lg 4 - 3 \times lg3 [ 4i\times (4/3)^i-12 (4/3)^i+12]+3 lg3 \times (4/3)^i- \frac{3}{4}lg3 $$
Since, we're finding only the asymptotic bounds, therefore, we can remove the constant terms, and moreover $n/3^i=1$ when $i=log_3n = k$. Therefore, doing that:
$$T(n) = 4^k \times T(1) + 3 lgn \times (\frac{4}{3})^k - 4k (4/3)^k +12\times /3)^k -12 +(4/3)^k \\= 4^{log_3n} + 3 log_2n \frac{4^{log_3n}}{n}-\frac{4 log_3n}{n}+\frac{4^{log_3n}}{n}-12$$
From this equation, we can see that the largest term is $4^{log_3n}$. Hence the asymptotic upperbound of the given recurrence is $O(4^{log_3n})=O(n^{log_34})$.
No comments:
Post a Comment