https://i.imgur.com/LuBRwcW.jpg
想問這兩題要怎麼證，我的想法是用
master theorem推第一題，但是卡在
Case3的條件二,他的f(n)是在theta 裡,
我不確定能不能直接固定theta裡c1,c2
來做推導，麻煩大家了

感覺兩個都是true把f(n)帶進去解mt就好了吧兩邊差距差蠻多的

和麟的作業題目XD應該第一題True，第二題False

樓上可以說為什麼第二題false嗎？沒feel

因為如果要用master theorem還有一個條件是af(n/b)<=cf(n), for some c<1,∀n，這樣才能適用case3

如果f(n)假設成n平方 a=2 b=2的話不就是1/2n平方<=cn平方c就可以取1/2 for all n這樣就可以用case 3了不是嗎？還是我這做法哪裡有問題？

噢噢，問題應該就是出在這題不能一開始就假設f(n)是n^2之類的函數，因為題目是給你一個集合，而如果要套用master theorem的話要for all n都符合下面那個式子，因此可以造出非常人工的函數使得每2次迭代都讓f(n)變成不一樣的函數(比如說n^2和n^4)