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 -> [imath]C_N = C_(N/2) + N[/imath]
That makes sense to me - every time we have we do something to all the elements in the current set hence [imath]+N[/imath]. This converges to [math]N/2 + N/4 + N/8 + ... = 2N[/math]. 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 -> [imath]C_N = 2C_{N/2} + N[/imath]. 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?
1. This recurrence arises for a recursive functions that halves the input, but perhaps must examine every item in the input -> [imath]C_N = C_(N/2) + N[/imath]
That makes sense to me - every time we have we do something to all the elements in the current set hence [imath]+N[/imath]. This converges to [math]N/2 + N/4 + N/8 + ... = 2N[/math]. 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 -> [imath]C_N = 2C_{N/2} + N[/imath]. 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?