a.
so, we have geometric series:
T(n)=n2+5n2/16+25n2/256+...=n2/(1−5/16)
T(n)=Θ(n2)
c.
Comparing with T(n)=aT(n/b)+f(n) :
a=3,b=4
so, we have:
f(n)=Ω(nlogba)=Ω(nlog43)
by Master Theorem:
T(n)=Θ(f(n))=Θ(n2)
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)≥nlog5n and T(n)≤nlog5/2n
so,
T(n)=Θ(nlogn)
g.
for recursion tree:
there are log∗(n) levels, and each subproblem at level i has one problem of size log(i)n
where log(i+1)n=log(log(i)n) and log(i)n=logn
So, the upper bound we have:
T(n)=logn+T(logn)=O(i=0∑log∗(n)log(i+1)n)=O(logn)
This is true because logn<1/2 for large n, and log(i+1)n<2i1logn and use geometric series.
Also, T(n)=Ω(logn)
so,
T(n)=Θ(logn)
j.
Comparing with T(n)=aT(n/b)+f(n) :
a=1,b=4/3
f(n)=1/n
so, we have:
logba=log4/31=0
nlogba=nlog4/31=1
f(n)=O(nlogba)=O(nlog4/31)=O(1)
then, by Master Theorem:
T(n)=Θ(nlog4/31)=Θ(1)
h.
T(n)=T(n1/4)+1=T(n1/16)+2=T(n1/64)+3=T(n1/4n)+n
T(n)=O(n)
i.
T(n)=n+7T(n)n=7n(7T(n1/4)n1/4+n1/2)+n=
=7kn1/2+1/4+1/8+...+1/2kT(n1/2k)+...+n
1/2+1/4+1/8+...+1/2k=1−1/2k
let n1/2k=2 , then:
T(n)=7nT(2)n/2+...+n
T(n)=O(7nn)
f.
T(n)=(n/(n−5))T(n−1)+1
T(n)=(n−5n)n−1T(1)+(n−5n)n−2+...+1
T(n)=O(1)
Comments
Leave a comment