How to calculate complexity of an algorithm?

Question

I've trying to calculate complexity of an algorithm, but I'm not sure how to do that. I know how to solve simple algorithms, but I'm struggling with recursion.

There is the code of recursion:

static int F(int m, int n)
    {
        if (n == 0)
            return m;

        if (m == 0 && n > 0)
            return n;

        else
            return Math.Min((1 + F(m - 1, n)), Math.Min((1 + F(m, n - 1)), (D(m - 1, n - 1) + F(m - 1, n - 1))));
    }

Can someone explain me or help me to calculate this function? I've tried googling it but I can find only simple examples.(maybe mine code is also simple?)

Thank you!

TsReaper · Accepted Answer · 2017-05-25 10:00:16Z

2

I don't know what the D function is in your first piece of code. I'll consider it as a constant function.

The first piece of your code is equivalent to the following one.

static int F(int m, int n)
{
    if (n == 0 || m == 0)
        return n + m;
    else
        return Math.Min((1 + F(m - 1, n)), Math.Min((1 + F(m, n - 1)), (D(m - 1, n - 1) + F(m - 1, n - 1))));
}

It's a little difficult to calculate the time complexity of a recursive function with two parameters, but we can estimate it roughly. We have the following equation.

T(n, m) = T(n-1, m) + T(n, m-1) + T(n-1, m-1)

We can discover that the equation is quite similar to the recursive equation of binomial coefficient, but with even larger result. This tells us that the time complexity of the algorithm is an exponential function, which is quite slow.

But actually, you can use some tricks to reduce its time complexity to O(mn).

bool calculated[MAX_M][MAX_N];
int answer[MAX_M][MAX_N]

static int F(int m, int n)
{
    if (n == 0 || m == 0)
        return n + m;
    else
    {
        if (calculated[m][n] == false)
        {
            answer[m][n] = Math.Min((1 + F(m - 1, n)), Math.Min((1 + F(m, n - 1)), (D(m - 1, n - 1) + F(m - 1, n - 1))));
            calculated[m][n] = true;
        }
        return answer[m][n];
    }
}

I can't quite understand what the second piece of code is going to do as there are lots of functions unprovided in your code. Maybe you can explain that a bit?

edited May 25, 2017 at 10:00

answered May 25, 2017 at 1:01

TsReaper

8557 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

TsReaper Over a year ago

Yes, you are right. Sorry for the incorrect answer I made previously. I've updated the answer now.

Collectives™ on Stack Overflow

How to calculate complexity of an algorithm?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related