含线性与对数递归调用的函数Big-O复杂度分析问询

def f(n):
    if n <= 1: 
        return 1
    return f(n-1) + f(n//2)

此处n//2表示对n做向零取整除法，例如3//2结果为1。

这是我在算法课程中遇到的问题。我原本认为该函数的时间复杂度应为指数级：
f(n-1)调用占主导地位，递归树的深度至少为n，每个分支会产生两个调用，因此复杂度呈指数级，f(n//2)的调用因被主导而不会对复杂度产生影响。

但给出的选项为：

• O((logn)²)
• O(nlogn)
• O(n(logn)²)
• O(n²)

我认为这些选项都不符合该场景。

需要说明的是，相比答案我更关注推导逻辑。由于这是Big-O而非Θ，存在多个可能的答案。我认为最优上界是O(nlogn)，这是结合线性与对数递归调用得出的，但该上界可能过低。希望有人能给出这类递归Big-O问题的直观解释。

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