0

My approach: I counted the number of operations performed (with some effort), and the result was $\log(e)$. But, How can determine this with Master Theorem?, any hints, Thanks! : I counted the number of operations performed (with some effort), and the result was $\log(e)$. But, How can determine this with Master Theorem?, any hints, Thanks!

MathUser
  • 335
  • Are you trying to estimate the sequence $(T(n))$ defined by $$T(2n)=T(n)+1\quad T(2n+1)=T(n)+2\quad T(0)=1\ ?$$ – Did Sep 28 '16 at 16:02
  • This $x^e$ notation... is it $x$ in power $e$? – HEKTO Sep 28 '16 at 19:47
  • @HEKTO Hi!, yes I refer to $x$ in power $e$, thanks! – MathUser Sep 29 '16 at 00:35
  • @Did How you determine this function?, i.e., this equation Is sufficient to determine the solution? – MathUser Sep 30 '16 at 00:48
  • I just tried to make sense of the question, at present rather difficult to understand. But you should know what you are asking, no? So, does it correspond to what I wrote or not? – Did Sep 30 '16 at 04:48
  • @Did - it's about how to apply the Master Theorem to this exponentiation algorithm analysis (for example, to compute $x^4$ we need to compute $x^2$ once and then square the result, etc. for bigger powers) – HEKTO Sep 30 '16 at 19:43

1 Answers1

0

Algorithm "Square and Multiply" is used to calculate exponent $x^n$, where $x$ can be anything (may be, even a matrix!) and $n$ is an integer. Basic operations are squaring ($x^2$) and multiplication ($x \cdot y$).

They usually assume that both these operations have the same time complexity $O(1)$. Also it usually assumed that the number $n$ is itself is power of two. In this case the following recurrent equation describes time complexity $T(n)$ of this algorithm:

$$T(n) = T(\frac{n}{2}) + O(1)$$ $$T(1) = O(1)$$

According to the Master Theorem (Case 2) its solution is:

$$T(n) = O(\log n)$$

because in this case $a = 1, b = 2, c = 0$.

HEKTO
  • 1,404