三类函数时间复杂度计算咨询，含三阶递归函数是否为O(3^n)验证

• 实现n * 5乘5操作、n + 5加5操作的两类函数，时间复杂度均为O(1)：这两类都是常数级运算，执行步骤不会随输入值n的大小变化，不管n是多少都只需要一次算术运算就能得到结果。
• 你给出的三重递归函数：

def func(n):
    if n <= 0:
        return 1 
    return func(n-1) + func(n-2) + func(n-3)

你提到的时间复杂度为O(3^n)的说法是正确的，这是该函数时间复杂度的合法上界。
原理很简单：每一次调用func(n)都会触发3次新的递归调用，递归深度最多为n层，所有层的总调用数上限是等比数列求和3^0 + 3^1 + ... +3^n，结果约等于3^n，因此上界可以表示为O(3^{n)*。如果要更精确的紧确复杂度，可以表示为*O(1.839}n)，这个底数是三元斐波那契数列的特征方程x^3 = x^2 +x +1的实根，不过日常分析中直接用*O(3^n)*表述也是完全没问题的。

内容的提问来源于stack exchange，提问作者Jishnu