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?