0
$\begingroup$

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.

Note: the question isn't about the value of mystery(n), but rather about the number of additions!

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ But how can I come up with this solution with the help of the Master theorem? $\endgroup$
    – SlaMath
    Apr 21, 2019 at 8:42
  • 1
    $\begingroup$ I never use the Master theorem, so I don't know. For problems like this, you don't need it. And, in my opinion, if you are going to use the so-called Master theorem, you should thoroughly understand its statement and proof. In other words, you should not need to ask this question. You should also know when it should not be used. $\endgroup$ Apr 21, 2019 at 20:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .