T(n) = T(n/10) + T(an) + n，如何解决这个问题？

更新：我仍在寻找不使用外部资源的解决方案。

Given: T(n) = T(n/10) + T(an) + n对于一些a， 然后：T(n) = 1 if n < 10，我想检查以下是否可能（对于某些a值，我想找到最小的可能 a):

For every c > 0 there is n0 > 0 such that for every n > n0, T(n) >= c * n

我尝试一步步打开函数声明，但它变得非常复杂，而且我陷入了困境，因为我根本看不到任何进展。

这是我所做的：（抱歉添加图像，那是因为我在word上写了很多，我无法将其粘贴为文本）

有什么帮助吗？

调用阿克拉-巴齐，g(n) = n1，因此临界指数为 p = 1，因此我们需要 (1/10)1 + a1 = 1，因此 a = 9/10。

直观上，这就像合并排序递归：每次调用都有线性开销，如果我们不减少子问题的总大小，我们最终会在运行时间中得到一个额外的日志（这将超过任何常数 c） 。