问一个复杂度的问题

function：
def f(n):
  if n < 4:
    return 1
  return f(n/2) + f(n/2)

复杂度不是O(lgN)?

最后一行改成 return 2*f(n/2) 才是复杂度O(lgN)吧？

明显是的，

补充内容 (2019-3-15 08:10):
说错了，不是

我咋觉得是O(n)呢，递归式写出来应该是T(n)=2*T(n/2)，用主方法解这个递归式解出来应该是O(n)，或者画递归树解也可以。不知道理解的对不对，如有错误请指教

Height of the tree(h)  =  log2(n)

Number of leaves  =   2^h=2^log2(n)=N