master theorem

Work in Progress

Summary

Master theorem

Concept

Master Theorem

T(n)ncworkT(n=b)(n=b)cwork¢¢¢T(n=b)(n=b)cworkT(n=b2)(n=b2)cwork¢¢¢T(n=b2)(n=b2)cworkT(n=b2)(n=b2)cwork¢¢¢T(n=b2)(n=b2)cwork............T(1)T(1)¢¢¢T(1)¢¢¢T(1)T(1)level0level1level2...levellogbn1nodeanodesa2nodes...alogbn=nlogbaleavesheight=logbnAtlevelk:aknodes,eachwithwork¡nbk¢c.Totalworkatlevelk:ak¡nbk¢c=nc¡abc¢k.

Application