if else recursion worst time complexity

user_3529352 0
Viewed 868

I have some trouble to figure out the worst time complexity of below code.
(This is not a homework, see https://leetcode.com/problems/integer-replacement/description/.)

int recursion (int n) {
    if (n == 1)
        return 0;
    if (n % 2 == 0) {
        return recursion(n/2) + 1
    } else {
        return min(recursion(n / 2 + 1) + 1, recursion(n - 1)) + 1;
   }
}

The only thing I know is when N == 2 ^ k(k > 0), worst time complexity is O(logN). However, I am unclear when N is not 2^k. Because even number / 2 can still get odd number. Some people said it is still O(LogN), but I am not convinced.

I know the code is not best solution, just wanna analyze the time complexity. I tried recursion tree and aggregate analysis, seems not help.

recursion c algorithm
1 Answers

If n is even, we know that T(n) = T(n/2) + 1, and if n is odd we know that T(n) = T(n/2 + 1) + T(n-1) + 1. In the latter case, as n is odd we know that n-1 must be even. if n/2 + 1 is even T(n) = T(n/4) + T(n/2) + 3 and if n/2 + 1 is odd T(n) = 2*T(n/4) + T(n/2) + 3.

From the above discussion, in the worst case T(n) is defined based on the T(n/2) and T(n/4) in a general case. From Akra-Bazzi Theorem we can say, T(n) = O(n^((log(1+sqrt(5))-log(2))/log(2))) ~ O(n^0.69) (from the first case) and T(n) = O(n) from the second case (which n/2 + 1 is odd).

However, for the more tight complexity, we should scrutinize more in our analysis.

user_37688710
Related