recurrence relations

Work in Progress

Concept

Proving merge sort

T(n)nworkT(n=2)n=2workT(n=2)n=2workT(n=4)n=4workT(n=4)n=4workT(n=4)n=4workT(n=4)n=4work............T(1)T(1)¢¢¢T(1)¢¢¢T(1)T(1)level0level1level2...levellog2n1node2nodes22=4nodes...2log2n=nleavesheight=log2nAtlevelk:2knodes,eachwithworkn2k.Totalworkperlevel:2kn2k=n.ThereforeT(n)=£(nlogn).

Application

Extra

Swapping base and power