1
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 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, 2017 at 9:30

2 Answers 2

Reset to default
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.

Improve this answer
$\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)$

Improve this answer
$\endgroup$

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