Divide and Conquer Recurrence Relation

Question

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.

Answer 1

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} $$