# Using O-notation for asymptotic estimation of the number of additions in recursive function

Consider the following python program:

def mystery(n):
if n==0:
return n * n
return 2 * mystery(n//3) + 4 * n


Let call the number of additions that are executed during the calculation a(n).

How can I find an asymptotic estimation for the function mystery(n) with the help of the O-notation and master theorem.

I tried to solve this problem and came up with the following solution, but I don't know if I'm right or wrong:

if $$n \geq 1$$, Assume that the function f(n) satisfies the recurrence relation: $$f(n)=1.f(n/3) + 1.n^0$$ We want to analyse the asymptotic growth of f with the help of the master theorem. Defining $$\alpha=1, \beta= 3,\delta=0$$

we see that the recurrence relation for f can be written as $$f(n)=\alpha.f(n//\beta,)+O(n^\delta)$$

Furthermore, we have $$\alpha= 1 = 3^0 = \beta^\delta$$ Therefore, the second case of the master theorem tells us that $$f(n) \in O(\log_\beta(n).n^\delta)= O(\log_3(n).n^0)= O(\log_3(n))$$

$$mystery(n)$$ computes $$mystery(n/3)$$ and then does one addition.
Therefore $$a(n) = a(n/3)+1$$.
Therefore, there is one addition each time $$n$$ is divided by 3.
So, the number of additions is within 1 of $$\lfloor \log_3(n) \rfloor$$.