HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Can I simplify the recurrence T(n) = 2T((n+1)/2) + c by ignoring the "+1" part?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
canthepartrecurrencesimplifyignoring

Problem

I have written a recurrence relation to describe a recursive algorithm finding the maximum element in an array. The algorthim has an overlap, meaning both of the subarrays that are recurred on contain the middle element of the array.

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

However, I want to simplify this recurrence relation more.

Since you can often times omit floors and ceilings in recurrence relations, can I omit the $+ 1$?

If so, then my relation is now: $T(n) = 2T(n/2) + c$

Would this alter my big-Theta time complexity? Why or why not?

Solution

This probably does not change the asymptotic order.

From $T'(n) = 2 T'(n/2) + c$, you can obtain $T'(n) = \Theta(n)$.

Then you can try to prove that your original $T(n) = \Theta(n)$ by mathematical induction.

Context

StackExchange Computer Science Q#52298, answer score: 4

Revisions (0)

No revisions yet.