https://i.imgur.com/LuBRwcW.jpg
想问这两题要怎么证，我的想法是用
master theorem推第一题，但是卡在
Case3的条件二,他的f(n)是在theta 里,
我不确定能不能直接固定theta里c1,c2
来做推导，麻烦大家了
感觉两个都是true把f(n)带进去解mt就好了吧两边差距差蛮多的
作者:
kyrie77 (NTU KI)
2019-03-27 01:01:00和麟的作业题目XD应该第一题True，第二题False
作者:
kyrie77 (NTU KI)
2019-03-27 19:40:00因为如果要用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了不是吗？还是我这做法哪里有问题？
作者:
kyrie77 (NTU KI)
2019-04-08 20:21:00噢噢，问题应该就是出在这题不能一开始就假设f(n)是n^2之类的函数，因为题目是给你一个集合，而如果要套用master theorem的话要for all n都符合下面那个式子，因此可以造出非常人工的函数使得每2次迭代都让f(n)变成不一样的函数(比如说n^2和n^4)