5
$\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?

Improve this question
$\endgroup$
4
  • 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.

Improve this answer
$\endgroup$
0
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.

Improve this answer
$\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.