Multiplication algorithm

Question

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!

Answer 1

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