■T(n)=aT(n/b)+O(nd) rm二z ifd logb a O(ndlogn) if d logb a if'd logb a. Merge sort:T(n)<2T(n/2)+0(n). a=b=2,d=1.So d=logb a. By the master theorem:T(n)=0(n logn). 10◼ 𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑂(𝑛 𝑑 ) ◼ Merge sort: 𝑇(𝑛) ≤ 2𝑇(𝑛/2) + 𝑂(𝑛). ◼ 𝑎 = 𝑏 = 2, 𝑑 = 1. So 𝑑 = log𝑏 𝑎. ◼ By the master theorem: 𝑇(𝑛) = 𝑂(𝑛 log 𝑛). 10