Time complexity of recursive function that calls two halves floor(x / 2) and ceil(x / 2)-CodePudding

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!

CodePudding user response：

You can prove by induction that the worst case input of bit length n is 2^{n 1} - 1, and the worst case even input of bit length n is 2^{n 1} - 2.

confirm that this is true for bit length 2 -- 2 is the only even input, and 3 is worse.
Let w_n be the worst case input of size n. If the premise is true for size n, then it is true for size n 1, because the worst case even input of size n 1 will recurse on the worst case for size n, and the worst case odd input size n 1 will recurse on the worst odd and even cases for size n.

Then you just need to show that, in processing the worst case, every input is of the form 2^{n 1} - 1 or 2^{n 1} - 2, and there are only O(log N) of those.

CodePudding user response：

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:

second significant bit is 0 then (x - 1) / 2 is even and (x 1) / 2 is odd.
second significant bit is 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).