patternMinor
Can I simplify the recurrence T(n) = 2T((n+1)/2) + c by ignoring the "+1" part?
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?
$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.
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.