Order of growth of specific recursive function

问题:

What is the order of growth of the following function?

    static int counter = 0;

    static void Example(int n)
    {
        if (n == 1) return;

        for (int i = 0; i < n; i++)
        {
            counter++;
        }

        Example(n / 2);
    }

In order to solve it I have done the following:

I first got rid of the inner for loop in order to end up with:

    static void Example(int n)
    {
        if (n == 1) return;            

        counter++;

        Example(n / 2);
    }

By analyzing that I was able to tell that the order of growth of that method was log base 2 of n .

so I am thinking that the final answer will be log base 2 times something else. How can I figure it out?

回答1:

Let's look at both the original and the modified function. In the original function, you have the following amount of work done:

• A constant amount of work for the base case check.
• O(n) work to count up the number.
• The work required for a recursive call to something half the size.

We can express this as a recurrence relation:

• T(1) = 1
• T(n) = n + T(n / 2)

Let's see what this looks like. We can start expanding this out by noting that

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

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

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

= n + n/2 + (n / 4 + T(n / 8))

= n + n/2 + n/4 + T(n / 8)

We can start to see a pattern here. If we expand out the T(n / 2) bit k times, we get

T(n) = n + n/2 + n/4 + ... + n/2^k + T(n/2^k)

Eventually, this stops when n / 2^k = 1. When this happens, we have

T(n) = n + n/2 + n/4 + n/8 + ... + 1

What does this evaluate to? Interestingly, this sum is equal to 2n + 1, because the sum n + n/2 + n/4 + n/8 + ... = 2n. Consequently, this first function is O(n). We could have also arrived at this conclusion by using the Master Theorem, but it's interesting to see this approach as well.

---

So now let's look at the new function. This one does

• A constant amount of work for the base case check.
• The work required for a recursive call to something half the size.

We can write this recurrence as

• T(1) = 1
• T(n) = 1 + T(n / 2)

Using the same trick as before, let's expand out T(n):

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

= 1 + 1 + T(n / 4)

= 1 + 1 + 1 + T(n / 8)

More generally, after expanding out k times, we get

T(n) = k + T(n / 2^k)

This stops when n / 2^k = 1, which happens when k = log₂ n (that is, lg n). In this case, we get that

T(n) = lg n + T(1) = lg n + 1

So T(n) = O(lg n) in this case.

Hope this helps!

回答2:

Let's see now.. this will add 1 to the counter n times. each call n is reduced by half until it reaches one.

You can get rid of the loop and use

counter+=n;

instead, because basically the loop adds n to counter, 1 by one.

This means that n will be added to the counter each time it runs, and then become smaller by 2 until it reaches one.

so say n = 40. counter: 40 -> 60 -> 70 -> 75 -> 77 -> 77. n: 40 -> 20 -> 10 -> 5 -> 2 -> 1.

Just a push in the right direction (counter+=n; being the important part)