# Determining time complexity of this function in python [duplicate]

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$?

• "Because it's recursive, I think it's $\mathcal{O}(\log n)$." There are plenty of recursive algorithms that aren't $O(\log n)$ and plenty of $O(\log n)$ functions that aren't recursive. You may have the right answer (I've not checked) but you certainly don't have the right reason. – David Richerby Nov 22 '17 at 9:30

Yes, it ist $O(\log_2 n)$, because only the first recursive call g(x_div) matters, and the argument is halved each time. The remainder of a divison by 2 is at most 1, which leads to $O(1)$ for this part of the recursion.
Let $T(x)$ denote the running time of the algorithm. The following recurrence captures the running time of the algorithm:
$T(x)=T(\frac{x}{2})+c,\ x\geq3,\ c \in O(1)$
where $T(0) = T(1) = a \in O(1)$
Solving this we get, $T(n) \in O(log_2 x)$