big-o - 如果以下解决方案是主定理的案例 3，则不是肯定的

Question

所以我想知道以下递归是否会被认为属于主定理的情况 3：T(n)=4T(n/2) + 10000 - 5000sin(n)。

所以我将我的答案标记为以下... A = 4, B = 2, F(N) = 10000 - 5000sin(n)

n^k = n^2

因此，当比较 F(n) 和 n^k 时，我们可以看到 f(n) 的增长速度比 n^k 快，这意味着这是主定理的情况 3。这个对吗？

标签： big-odiscrete-mathematicsrecurrencemaster-theorem

Answer 1

因为 -1 ≤ sin(n) ≤ 1，所以 5000 ≤ f(n) ≤ 15000，这是 O(1)，因为它永远不会随着输入大小而增长。

这是情况三，因为 f(n) 是常数时间 ( O(1)== n ⁰ )，它渐近小于 n ^{log ₂ 4}。因此，根据主定理，您的递归关系 T(n) = Θ(n ² )。