c++ - 求解T(n)<T(7n/10)+kn+b

Question

求解T(n)<T(7n/10)+kn+b的时间复杂度，k>0.
这题答案是O(n)，但是我求不出来。

Answer 1

a = 1, b = 10/7, 로그_ba = 0
f(n) = n¹ 여기서 1 > 로그_ba = 0

7n/10 <= kn, k = 7/10
所以용 마스터 정리 사례 3,
T(n) = Θ(n)