worst case runtime for if-else recurrence

Question

The question is asking worst-case time complexity of g(n), I'm confused about why the second equation is c1n, not c1n^2.

I think the worst-case should have larger complexity right? Or it's because the "b" in the second branch of if-else is bounded and thus treated as a constant? If so, how about the recurrence? Will the recurrence also have a constant complexity because n becomes a constant in this case?

Answer 1

The trick here is that the else branch is almost never chosen.

You can calculate the first few values:

g(0) == 1
g(1) == 1

g(2) == 4
g(3) == 4

g(4) == 16
g(5) == 16
g(6) == 16

then for every n >= 4:
g(n) >= 16 > 5.

Hence for every n >= 12, g(n/3) > 5.

So in any execution, the else branch is chosen at most twice, in the last two recursive calls, with values of n less than 11.

To be perfectly pedantic, I think the answer should say the constant cost c0 applies for n <= 11.