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

user_16687227 0
Viewed 73

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!

brute-force dynamic-programming math time-complexity algorithm
1 Answers

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

user_136443770
Related