Confusion with recurrences: C_N = C(N/2) + N, N/2 + N/4 + N/8 + ... = 2N

[Mondo]

I have stumbled upon two examples of recursively defined functions:

1. This recurrence arises for a recursive functions that halves the input, but perhaps must examine every item in the input -> $C_N = C_(N/2) + N$
That makes sense to me - every time we have we do something to all the elements in the current set hence $+N$. This converges to $$N/2 + N/4 + N/8 + ... = 2N$$. All clear.

But next author defines another recursive function: This recurrence arises for a function that has to make a linear pass through the input before, during or after splitting that input into two halves -> $C_N = 2C_{N/2} + N$. The problem is why we multiply it by 2? We basically do a linear pass thru elements so it should be same as in the previous case #1, namely just add N.

So what do I miss here?

 

[blamocur]

What does this all mean? Can you copy-paste the exact statements and definitions you are referring to?
Thank you.

 

[Mondo]

@blamocur here is the formula I have problem with

The question is why $$2C_{N/2}$$? Why multiply by 2?

 

[Dr.Peterson]

You need to also give us enough context so we know what $C_N$ means, and so on.

Also, please show the one you said you understood, for comparison. That one didn't make sense to me! (There, I don't see why you didn't multiply by 2! And the sum was even wrong.)

 

[Mondo]

Okay, so here is the one I do understand

@Dr.Peterson I don't understand why do you say the sumis wrong? It is elementary sum of $\frac{1}{2^n}$ and it does converge to 2.
As for what $C_{N}$ means - it is just a function defined recursively (probably the notation here is slightly abused). The point here is this. For every iteration we do something to all the elements hence we need to add N. Since we have N, N/2, N/4 such actions and we stop at 0 the number of operations taken is 2N. This is very clear. However formula 2.4 is not clear because there, in its description author says it arises when we need to do a "linear pass" thru the input. And this is exactly the case of formula 2.3! In 2.4 and 2.4 we need to do something to every input element - hence we add N. But why he decided to multiply it by two is a mystery to me.

 

[blamocur]

The question is why 2CN/22C_{N/2}2CN/2? Why multiply by 2?

Because at the next level of recursion you have to process both ,i.e. two, halves of your data?

 

[blamocur]

@Dr.Peterson I don't understand why do you say the sumis wrong? It is elementary sum of 12n\frac{1}{2^n}2n1 and it does converge to 2.

Because you start with $n=1$, not $n=0$.

 

[Mondo]

Because at the next level of recursion you have to process both ,i.e. two, halves of your data?

I thought so too but this can't be the case because regardless which halve you process it will always sum up to current N. Also, previous formula also does "something" to each element, in both halves and there they don't multiply by 2.

Because you start with $n=1$, not $n=0$.

Not true. You start with N then N/2, N/4, N/8 and so on until you hit N =1 in which case you return 0 so the last term in 0 not 1.

 

[Dr.Peterson]

@Dr.Peterson I don't understand why do you say the sumis wrong? It is elementary sum of $\frac{1}{2^n}$ and it does converge to 2.

Because you misquoted it:

This converges to $$N/2 + N/4 + N/8 + ... = 2N$$. All clear.

rather than



That is, in what you wrote, you started with n=1, not n=0!

 

[Mondo]

Yes, my bad I am sorry.
Do you agree that the Formula 2.4 is hard to understand? Especially in comparison to Formula 2.3, and we can't really justify that multiplication by two?

 

[Dr.Peterson]

Do you agree that the Formula 2.4 is hard to understand? Especially in comparison to Formula 2.3, and we can't really justify that multiplication by two?

The first example says,

2.3 This recurrence arises for a recursive program that halves the input, but perhaps must examine every item in the input.​

(I notice that you changed "program" to "function", which was part of what initially troubled me.)

My difficulty here is that I don't know what it means to "halve the input". Does it somehow go through all the input (in the worst case, as indicated by "perhaps") and drop exactly half of it, passing the other half to itself recursively? I was hoping you would give enough context to have a sense of what that means.

They translate this into $C_N=C_{N/2}+N$. That makes sense, given that, for some unknown reason, it only acts of half the data recursively.

[I note, incidentally, that if we start with $C_1=0$, we get the sequence $C_2=0+2=2$, $C_4=2+4=6$, $C_8=5+8=13$, and so on, and the sequence 0, 2, 6, 13 is, as they say, close to 2N = 0, 4, 8, 16 respectively.]

The second example says,

2.4 This recurrence arises for a recursive program that has to make a linear pass through the input, before, during, or after splitting that input into two halves.​

This makes sense to me, as they are using both halves, perhaps reading through all the data and then calling itself twice, first for one half and then for the other. This is what I expect of "divide and conquer". I don't know what to think of the other.

They translate this into $C_N=2C_{N/2}+N$. This make perfect sense to me, as the function is called twice with half the input, once for each half. Do you see why I find this one clearer than the other (though I'm still lacking contextual information, including exactly what $C_N$ is taken to mean)?

[In this case, if we start with $C_1=0$, we get the sequence $C_2=2*0+2=2$, $C_4=2*2+4=8$, $C_8=2*8+8=24$, and so on, and the sequence 0, 2, 8, 24 is, as they say, close to NlgN = 0, 2*1, 4*2, 8*3.]

 

[Mondo]

Wow, thank you very much @Dr.Peterson! You explained it really well and I finally got it! The problem I had was I didn't see a difference between formula 2.3 and 2.4 because in my eyes they were both working with the same amount of data. However this is not true because formula 2.3 works only with N number of items in every iteration, and that translates to N + N/2 + N/4 + ... = 2N as we halve the input every iteration. On the other hand formula 2.4 works with N number of elements as well but after halving it also processes the other half too - hence times 2.

To answer your question:

My difficulty here is that I don't know what it means to "halve the input"

Imagine you have a set of elements 1,2,3,4,5,6,7,8,9,10 (sorted) and you search for a first value less than 3. Then you can start say right in the middle, at 5 and decide if it more or less than my target 3? It is more, hence next you only process the lower half from 1-5 and completely drop the upper half 5 - 10. Does it make sense?

As for $C_N$ - this is the notation they use to describe recurrences. I agree it is not precise in a mathematical sense - the equal sign makes this equation incorrect, maybe they should have used "->" instead?