Question

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

Answer 1

T(n) = T(n/5) + T(7n/10) + n^2
Method 1 : By using Estimation method,

Let us consider R(n) = T(n/5) + T(n/5) + n^2
and S(n) = T(7n/10) + T(7n/10) + n^2
 Asymptotically, R(n) <= T(n) <= S(n)

For R(n) = 2T(n/5) + n^2
Using Master's Theorem,
 a = 2, b = 5
==> n^ log5 2
log2 4< log2 5 < log2 8
2< log2 5 < 3
==> 0.5 > log5 2> 0.3

In R(n), the second term dominates
R(n) = Theta(n^2)

S(n) = 2T(7n/10) + n^2

a = 2, b = 10/7

n^ log10/7 2

log10/7 10/7 < log 10/7 2< log 10/7 (10/7)^2
==> 1<log 10/7 2 < 2
In S(n) also the second term dominates
S(n) = Theta (n^2)

T(n) = Theta(n^2)/ O(n^2)

Method 2 : We can even solve this recurrence relation using substitution method,

Let us assume T(n) = O(n^2)
T(n) <= k(n/5)^2 + k(7n/10)^2 +n^2
T(n) <= k[(53/100) * n^2] + n^2
T(n) <= kn^2 + n^2 - k(47/100)*n^2
n^2 - k(47/100)* n^2 <=0
==> c >= 100/47

T(n) = O(n^2) ,for c >= 100/47

Answer 2

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)

Answer 3

assume T<= kn^2

found k

done

Answer 4

Using Estimation Method, we get

R(n) = 2T(n/5) + n²  & S(n) = 2T(7n/10) + n²

Applying Masters Theorem to both equations, we get

R(n) = O(n²)  & S(n) = O(n²) 

Hence, the time complexity for T(n) is O(n²).