0
$\begingroup$

enter image description here

I have this Divide and Conquer relation and I need to provide recurrance relation of it.

I got something like

$T(n) = 4T(n) + \lfloor\frac{n}{2}\rfloor$

but still confused whether this is right or wrong.

I got $4T(n)$ because the for-loop loops 4 times with no other extra lines.

However I am not quite sure about the

$+ \lfloor\frac{n}{2}\rfloor$ part.

Since the "printer($\lfloor\frac{n}{2}\rfloor$)" recursively calls the algorithm with $\frac{n}{2}$, I just added it at the end of the relation to show that it is being processed once every time the algorithm is called.

Is this right way to provide the recurrance relation?

Any help will be much appreciated.

Thank you.

$\endgroup$
1
$\begingroup$

Close, but $T$ should be "called" when the printer function calls itself recursively. Presumably, $T(n)$ counts the number of calls to printline. The recurrence [note": recurrEnce] relation ought to be: $$ \begin{align} T(1) &= 0 \\ T(n) &= 4 + T(\lfloor n/2 \rfloor) \quad \text{(n > 1).} \\ \end{align} $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You're welcome :) $\endgroup$ – BrianO Oct 31 '15 at 6:47

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.