What is the complexity of this tree recursive integer replacement algorithm?

Question

LeetCode has an Integer Replacement problem defined as follows:

Given a positive integer $n$, you can apply one of the following operations:

1. If $n$ is even, replace $n$ with $n / 2$.
2. If $n$ is odd, replace $n$ with either $n + 1$ or $n - 1$.

Return the minimum number of operations needed for $n$ to become 1ドル$.

I would like to determine the time and space complexity of a naive tree-recursive algorithm that uses memoization (caching to avoid recalculation). Here is the Python implementation:

class Solution:
 def __init__(self):
 self.results = {1: 0} # specifies 1 as the base case requiring 0 operations
 def integerReplacement(self, n: int) -> int:
 if n not in self.results:
 if n % 2: # n odd
 self.results[n] = 1 + min(
 self.integerReplacement(n + 1),
 self.integerReplacement(n - 1)
 )
 else: # n even
 self.results[n] = 1 + self.integerReplacement(n / 2)
 return self.results[n]

If this were tree recursive in all cases, the running time would be $O(2^n)$ because the branching factor is two; however, this is tree recursive only half the time. What is the time complexity of this algorithm? I am also interested in the space complexity, which I know would depend on the greater of the maximum stack depth and hash table size.

Answer 1

I figured out the answer to my question. The time complexity is $O(\log(n))$ because $n$ is halved every two calls (worst case). For more detail, see my solution.

Answer 2

Here, you can get away with branching in only one direction greedily. Thus, you can even convert the recursion into a simple while loop, which takes about $O(\log n)$ steps. Here is the code:

int integerReplacement(int n) {
 int count = 0;
 if (n == INT_MAX) {
 return 32;
 }
 while(n > 1){
 count ++;
 if ((n & 1) == 0) { // n is even
 n = n >> 1; // n = n/2
 } else { // n is odd
 if ((n & 2) == 0 || n < 4) { // 2nd last bit is zero or n is small
 n--; // n = n - 1
 } else {
 n++; // n = n + 1
 }
 }
 }
 return count;
}

If $n$ is odd, then adding or subtracting 1ドル$ makes it even, which will then be halved. If we somehow anticipate whether adding or subtracting will make it a multiple of 4ドル$, then we would rather go in that direction.

Now if $n~ mod~ 4 = 1$, then subtracting helps, whereas if $n~ mod~ 4 = 3$, then adding helps. By 'helps' I mean, you can perform (at least) two successive halvings. Thus we have an optimal greedy strategy at our hand.

For added effciency, I have converted the $mod$ operations into equivalent bitwise operations.

---

Now let us analyze your algorithm: Here we have $$T(n) = \begin{cases} T(n+1) + T(n-1) + c, & \text{when $n$ is odd}\\ T(n/2) + c, & \text{when $n$ is even} \end{cases}$$

Combining these two steps, we have $$T(n) \le T(\frac{n+1}{2}) + T(\frac{n-1}{2}) + 3c$$ Thus, we have $T(n) = O(n)$.

• codeR: You can see my solution there: leetcode.com/problems/integer-replacement/solutions/5215070/…
• Ellen Spertus: Thank you very much for your time and explanation, but what I'm looking for is a complexity analysis of my code. I will edit my question to make that clearer.