CODEWITHSUNDEEP
algorithmrecursioncomplexity-theory
user9044020
user9044020

Reputation:

Calculate complexity of recursion algorithm

func3(int n) {
    for (int i = 1; i<n; i++)
        System.out.println("*");
    if (n <= 1)
    {
        System.out.println("*");
        return;
    }
    if(n % 2 != 0) //check if odd
        func3(n - 1)
    func3(n / 2);
    return;
}

I need to calculate the complexity of this algorithm, how can i do it when i have for in my code and 2 calls to func3?

Upvotes: 0

Views: 223

Answers (1)

meowgoesthedog
meowgoesthedog

Reputation: 15035

The bit pattern of n is very helpful in illustrating this problem.

Integer division of n by 2 is equivalent to right-shifting the bit pattern by one place, discarding the least significant big (LSB). e.g.:

                          binary
                       ----------------------
n = 15                 |  0000 1111 
n / 2 = 7 (round down) |  0000 0111 (1) <- discard
  • An odd number's LSB is always 1.
  • An power-of-two only has 1 bit set.

Therefore:

  • The best case is when n is a power-of-2, i.e. func3(n - 1) is only called once at the end when n = 1. In this case the time complexity is:

    T(n) = T(n/2) + O(n) = O(n)

  • What is the worst case, when func3(n - 1) is always called once in each call to func3? The result of n / 2 must always be odd, hence:

    All significant bits of n must be 1.

    This corresponds to n equal to a power-of-two minus one, e.g. 3, 7, 15, 31, 63, ...

    In this case, the call to func3(n - 1) will not yield another call to the same function, since if n is odd then n - 1 must be even. Also, n / 2 = (n - 1) / 2 (for integer division). Therefore the recurrence relation is:

    T(n) = 2 * T(n/2) + O(n) = O(n log n)

One can obtain these results via the Master theorem.

Upvotes: 2

Related Questions