1
$\begingroup$

This question already has an answer here:

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

$\endgroup$

marked as duplicate by David Richerby, Evil, cody, Kaveh, Juho Dec 10 '17 at 11:31

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ "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. $\endgroup$ – David Richerby Nov 22 '17 at 9:30
0
$\begingroup$

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.

The result is the next greater power of 2 compared to the double of the number of bits of the input.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.