6
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ What have you tried and where did you get stuck? Hint: solve the simplified recurrence and prove the answer correct for the original one. See also our reference question. Oh, nitpick: "time complexity" is not a useful term here. You are solving a recurrence, period. $\endgroup$ – Raphael Jan 26 '16 at 11:19
  • $\begingroup$ I just used mathematical induction to prove that my recurrence relation is indeed $T(n) = \Theta(n)$. However, I'm just wondering if there's an easier way to justify me omitting the +1 without showing the inductive proof and just the Master Theorem proof. $\endgroup$ – leviless Jan 26 '16 at 17:36
  • $\begingroup$ There may be ways to generalize the proof you just performed to arbitrary $a$, $b$, $c$, and added constant. $\endgroup$ – Raphael Jan 26 '16 at 23:52
  • $\begingroup$ It's probably safe to go the extra mile and write the inductive proofs. I've generalized my inductive proofs with constants which should be enough. Thanks! $\endgroup$ – leviless Jan 27 '16 at 2:13
4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

We can rewrite the original recurrence as

$$T(n-1+1)=2T(\frac{n-1}2+1)+c$$ or, setting $m:=n-1$ and $S(m):=T(m+1)$,

$$S(m)=2S(\frac m2)+c,$$ which is of the simplified type.

After solving for $S(m)$,

$$T(n)=S(n-1)$$ and the solutions are virtually identical.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.