T(n)=aT(n/b)+f(n)
Then T(n) has the following asympotic bounds:
- If f(n)=O(nlogba−ϵ) for some constant ϵ>0, Then T(n)=Θ(nlogba)
- If f(n)=Θ(nlogba), Then T(n)=Θ(nlogbalgn)
- If f(n)=Ω(nlogba+ϵ) for some constant ϵ>0, and if af(n/b)≤cf(n) for some constant c≤1 and all sufficiently large n, then T(n)=Θ(f(n))
No comments:
Post a Comment