计算递归函数的大O

Question

我有一个方法来检查一个数组是否是堆。在每次递归调用时，我在左侧子树和右侧子树上创建2个新的递归调用来遍历节点并检查它们的值是否正确。

我想计算这个BigO。我认为在最坏的情况下，它是O（n），因为如果它是堆，那么它永远不会提前停止，并且需要访问每个节点。我认为最好的情况是O（3），当它检查第一个左侧子树和右侧子树并且两个都返回false（不是堆）时会发生这种情况。

我的问题是：这个逻辑是否有意义？我认为它确实如此，但是每当我看到递归函数的时间复杂度时，它们似乎总是处于对数时间的某种形式。对于没有人明确指出的递归函数来说，这几乎就像是神秘的质量。递归函数如何经常在对数时间内处理事物？我的上述逻辑有效吗？

Answer 1

是的它是有道理的。你看到大多数算法取对数时间的原因是因为它重复了某些事情，并且继续将范围除以某个因子。

Answer 2

是的，这是有道理的。 Master Theorem（尽管可以说是最有趣的）的三种情况中只有一种具有对数。