Find Out The Running Time Of A Recursive Algorithm (Master-Therorem)

Question

Here is the algorithm whose running time I want to calculate:

T(n) = {
        c0 * n, if n <= 20
        T(roundUp(n/4)) + T(roundUp(5/12 * n + 3/2)) + c1*n, if n > 20
       }

n is part of the positive natural numbers, c0 and c1 are constants.

Here is the algorithm in java-code:

    public static void main(String[] args) {
        for (int i = 20; i < 100; i++) {
            System.out.println("i: " + i + " :    " + rec(i, 1, 1));
        }
    }

    public static int rec(int n, int c0, int c1) {
        int res = 0;
        if (n <= 20) {
            res += c0 * n;
        } else {
            double temp = n / 4d;
            double temp2 = n * (5 / 12d) + (3 / 2d);
            res += rec((int) Math.ceil(temp), c0, c1) + rec((int) Math.ceil(temp2), c0, c1) + c1 * n;
        }
        return res;
    }

I'm looking for an approach or an explaining example.

Answer 1

Hmm, didn't do this for long time, but since nobody gave answer yet, let me try. You basically create tree here, with two important children. Left one is based on temp = n / 4d, and right one is based on temp2 = n * (5 / 12d) + (3 / 2d). So question is, how deep is this tree? Since n / 4d will end up under 20 quicker then n * (5 / 12d) + (3 / 2d) we care only about right child. So question is, how much far right children are there based on n? As we iterate, we have this:

n * (5 / 12d) + (3 / 2d) 
ceil(n * (5 / 12d) + (3 / 2d) ) * (5 / 12d) + (3 / 2d)
ceil(ceil(n * (5 / 12d) + (3 / 2d)) * (5 / 12d) + (3 / 2d) ) * (5 / 12d) + (3 / 2d)
...

Here, we can also ignore 3/2d part, as well as everything related to it, so we get this:

n * (5 / 12) ^ k < 20

Where k is the number of steps to reach most far right child, so we have:

n * (5 / 12) ^ k < 20
k = log_(5 / 12) (20 / n)
k = log_2(20 / n) / log_2 (5 / 12)   
k = (log_2 (20) - log_2(n) ) / log_2 (5 / 12)  

Since this:

k = log_2 (20) / log_2 (5 / 12) 

is a specific number, we can ignore it...

k = - log_2(n) / log_2 (5 / 12) 

Since:

log_2 (5 / 12)  < 0

we are left with:

k = log_2(n) = lgn

As expected, since we work only with tree, you get O(n) = lg(n).