I would like to determine the time complexity of this function, in $\mathcal{O}$-Notation.
def g(x):
if x == 0:
return 1
elif x == 1:
return 2
else:
x_div = x//2 # // is integer division
x_mod = x % 2
return g(x_div)*g(x_mod)
Because it's recursive, I think it's $\mathcal{O}(\log{}n)$. Is this correct? A small explanation would be great.
Another question, is there a relation between the return value of the function and the binary representation of $n$?