Answer to Question #280877 in Discrete Mathematics for jack

Question #280877

solve the following recurrence relations

a. 𝑇(𝑛) = 𝑇( 𝑛/4) + 𝑇( 𝑛/2 ) + 𝑛^2

b. T(n) = T(n/5) + T(4n/5) + n

c. 𝑇(𝑛) = 3𝑇( n/4 ) + 𝑐𝑛^2 

f. 𝑇(𝑛) = (𝑛/𝑛−5) * 𝑇(𝑛 − 1) + 1

g. 𝑇(𝑛) = 𝑇(log 𝑛) + log 𝑛

h. 𝑇(𝑛) = 𝑇 (𝑛^ 1/ 4) + 1

i. 𝑇(𝑛) = 𝑛 + 7 √𝑛 ∙ 𝑇(√𝑛)

j. 𝑇(𝑛) = 𝑇 ( 3𝑛/4 ) + 1/root(n)


1
Expert's answer
2022-01-04T17:50:13-0500

a.




so, we have geometric series:

T(n)=n2+5n2/16+25n2/256+...=n2/(15/16)T(n)=n^2+5n^2/16+25n^2/256+...=n^2/(1-5/16)

T(n)=Θ(n2)T(n)=\Theta(n^2)


c.

Comparing with T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n) :

a=3,b=4a=3,b=4

so, we have:

f(n)=Ω(nlogba)=Ω(nlog43)f(n)=\Omega(n^{log_ba})=\Omega(n^{log_43})

by Master Theorem:

T(n)=Θ(f(n))=Θ(n2)T(n)=\Theta(f(n))=\Theta(n^2)


b.





additive term is exactly the current subproblem size, so T(n) is simply the sum of all numbers that appear in this tree. the:

T(n)nlog5nT(n)\ge nlog_5n and T(n)nlog5/2nT(n)\le nlog_{5/2}n

so,

T(n)=Θ(nlogn)T(n)=\Theta(nlogn)


g.

for recursion tree:

there are log(n)log^*(n)  levels, and each subproblem at level i has one problem of size log(i)nlog^{(i)}n

where log(i+1)n=log(log(i)n)log^{(i+1)}n=log(log^{(i)}n) and log(i)n=lognlog^{(i)}n=logn

So, the upper bound we have:

T(n)=logn+T(logn)=O(i=0log(n)log(i+1)n)=O(logn)T(n)=logn+T(logn)=O(\displaystyle \sum^{log^*(n)}_{i=0}log^{(i+1)}n)=O(logn)

This is true because logn<1/2logn<1/2 for large n, and log(i+1)n<12ilognlog^{(i+1)}n<\frac{1}{2^i}logn and use geometric series. 

Also, T(n)=Ω(logn)T(n)=\Omega (logn)

so,

T(n)=Θ(logn)T(n)=\Theta(logn)


j.

Comparing with T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n) :

a=1,b=4/3a=1,b=4/3

f(n)=1/nf(n)=1/\sqrt n

so, we have:

logba=log4/31=0log_ba=log_{4/3}1=0

nlogba=nlog4/31=1n^{log_ba}=n^{log_{4/3}1}=1

f(n)=O(nlogba)=O(nlog4/31)=O(1)f(n)=O(n^{log_ba})=O(n^{log_{4/3}1})=O(1)

then, by Master Theorem:

T(n)=Θ(nlog4/31)=Θ(1)T(n)=\Theta(n^{log_{4/3}1})=\Theta(1)


h.

𝑇(𝑛)=𝑇(𝑛1/4)+1=𝑇(𝑛1/16)+2=𝑇(𝑛1/64)+3=𝑇(𝑛1/4n)+n𝑇(𝑛) = 𝑇 (𝑛^{ 1/ 4}) + 1=𝑇 (𝑛^{ 1/ 16}) + 2=𝑇 (𝑛^{ 1/ 64}) + 3=𝑇 (𝑛^{ 1/ 4^n}) + n

T(n)=O(n)T(n)=O(n)


i.

𝑇(𝑛)=𝑛+7𝑇(𝑛)n=7n(7T(n1/4)n1/4+n1/2)+n=𝑇(𝑛) = 𝑛 + 7 𝑇(\sqrt𝑛)\sqrt n=7\sqrt n(7T(n^{1/4})n^{1/4}+n^{1/2})+n=


=7kn1/2+1/4+1/8+...+1/2kT(n1/2k)+...+n=7^kn^{1/2+1/4+1/8+...+1/2^k}T(n^{1/2^k})+...+n


1/2+1/4+1/8+...+1/2k=11/2k1/2+1/4+1/8+...+1/2^k=1-1/2^k


let n1/2k=2n^{1/2^k}=2 , then:

𝑇(𝑛)=7nT(2)n/2+...+n𝑇(𝑛)=7^nT(2)n/2+...+n

𝑇(𝑛)=O(7nn)𝑇(𝑛)=O(7^nn)


f.

𝑇(𝑛)=(𝑛/(𝑛5))𝑇(𝑛1)+1𝑇(𝑛) = (𝑛/(𝑛−5)) 𝑇(𝑛 − 1) + 1


T(n)=(nn5)n1T(1)+(nn5)n2+...+1T(n)=(\frac{n}{n-5})^{n-1}T(1)+(\frac{n}{n-5})^{n-2}+...+1


T(n)=O(1)T(n)=O(1)

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment