http://i.imgur.com/iHZ6v3V.jpg
題目在圖上 求big oh
遞回怎麼去假設出式子 再求時間複雜度
某方面來講你已經寫完了T(n)=2*T(n/2)+2*T(n/2)=4T(n/2)=16T(n/4)...
喔喔 他是用master method做的 直接代入就好n^log2(2)=n > 常數 所以T(n)=theta(n)
這題我是分析 一個母問題切割成兩個子問題 可是MM的公式T(n)=aT(n/b)+f(n)這種形式才可使用這題怎麼用MM去看
因為他寫recursive部分的theta(1)那邊 那個是指乘法和加法的部分 這個是是為常數 而且是每層遞增所以符合f(n)的條件