I have a function f(x) that calls f(x / 2) if x is even and calls both f((x + 1) / 2) and f((x - 1) / 2) if x is odd. Note that f(1) = constant and we don't recurse further than f(1). (So, it can be said that f(1) is the base condition.)
If I memoize f(x), what will be the time complexity of computing f(x)? Will it be O(2 ^ n) because two functions are called at every level, or will it improve because of memoization?
I tried some cases by hand, and it seems that the complexity is no more than O(log n) and only two new functions are called at every level of recursion. (If I don't memoize, it does seem to be O(2 ^ n))
I'd be glad if someone could help me with the complexity. Thanks!
Let's consider some number x written in binary as x = 11001.
If x is even then it's lsb(least significant bit) is 0 and we have f(x) = f(x / 2).
If x is odd then it's lsb is 1 and depending on the second significant bit we will have two cases:
0 then (x - 1) / 2 is even and (x + 1) / 2 is odd.1 then (x - 1) / 2 is odd and (x + 1) / 2 is even.In both cases we will have f(x) = f(someEvenNumber) + f(someOddNumber).
This means any bit in the number will cost either 1 operation if this bit is not set, and 1 operation + f(y) where y is < x / 2). The number of these bits is at most log (x) so total complexity will be 2 * log(x) which is same as log (x).