Deriving a recurrence equation and apply Master's Thrm to it

43 Views Asked by At

So for a function such as:

function Hi(n)
if n > 1 then
for j ← 1 to n
    do print(”Hi”)
Hi(n/2)
Hi(n/2)
Hi(n/2)

It's very easy to eyeball this and get a recurrence of:

T(n) = 3(n/2) + n

And then applying Master's Theorem to get its Big Ɵ is also very straightforward.

But what confuses me is what do I do when there's some code after the recursive calls and the base case happens are n < (some number greater than 1), like this:

Function PrintZs (integer n)
    if n < 3
        print(“Z”)
    else
        PrintZs(n/3)
        PrintZs(n/3)
        PrintZs(n/3)
        for i ← 1 to 2n do print(“Z”)

Here 2 things are different: the base case has n < 3 rather than n < 1, and there

My thought is that the recursive function will be:

T(n) = 3T(n/3) + 2n + 1

I'm ignoring the fact that the base case happens at n < 3 rather than n < 1 because this only takes off 1 level of the recursive calls, which is an irrelevant amount. 2n is obviously there for the 2n prints, which will only happen when n >= 3.

Then when I apply master's theorem to this problem, I will treat the equation as:

 T(n) = 3T(n/3) + 2n

Since that 1 print call in the if statement is irrelevant to the 2n print calls that happen every call to the function (where n >= 3).

Is my thought process correct? If not, what needs to be changed?