Solve the recurrence Relation T(n)=T(n/5)+T(7n/10)+(n^2)

1 Answer

0 votes

Almost the same.

Assume that T(n) <= (100/47)c(n^2), where c is a constant.

Prove it by induction:

First, there is T(1) = O(1), satisfying that T(1) <= (100/47)c*1*1.

Assume that T(m)<=(100/47)c(m^2) for all m <= n-1

thus, for n, we have T(n) <= T(n/5) + T(7n/10) + cn^2

since n/5 <= n-1, 7n/10 <= n-1

For n, there is:

T(n) <= (100/47)c * (n/5)^2 + (100/47)c * (7n/10)^2 + cn = (4/47)cn^2 + (49/47)cn^2 + cn^2 = (100/47)cn^2

Thus, T(n) <= (100/47)cn^2 for all n's. So that T(n) = O(n^2)

For how to get 100/47:

it comes from that:

1/(1-(1/5)^2-(7/10)^2))=100/47

that is to say, we assume n^2 to be the "1" (think about what it stands for)

answered Feb 8 by Hao Wen (196 points)
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...