Processing math: 100%

Thursday, March 27, 2014

Master Theorem of Dive-and-Conquer

T(n)=aT(n/b)+f(n)
Then T(n) has the following asympotic bounds:
  1. If f(n)=O(nlogbaϵ) for some constant ϵ>0, Then T(n)=Θ(nlogba)
  2. If f(n)=Θ(nlogba), Then T(n)=Θ(nlogbalgn)
  3. If f(n)=Ω(nlogba+ϵ) for some constant ϵ>0, and if af(n/b)cf(n) for some constant c1 and all sufficiently large n, then T(n)=Θ(f(n))

No comments:

Post a Comment