Now, $\color{blue}{\text{Exponentiation}}$ is defined as
Exponentiation is a mathematical operation, written as $b^n$, involving two numbers, the base $b$ and the exponent or power $n$, and pronounced as "$b$ raised to the power of $n$".
$$b^n = \underbrace{b\times b\times\cdot \cdots \times b}_{n\text{ times}}$$
Now, my primary question is that What is the Time Complexity of Exponentiation Operation as per RAM Model of Computation?
- As per this, RAM Model assumes a computer can do Exponentiation in a single unit-cost instruction. $(\mathcal{O}(1))$
- Intuitively, it appears to be of $\mathcal{O}(n)$
- Now, What is the time complexity of in-built
pow
functions in many programming languages? One comment claims it be of $\mathcal{O}(\log n)$. And does**
operator in Python has the same complexity as that ofpow
?
Adding to this, the $n^{th}$ Fibonacci Number can be computed in atleast four ways
- Using $F(n)=F(n-1)+F(n-2)$, Time Complexity of this is essentially $\mathcal{O}(2^n)$ [using Master's Theorem]
- Using Memoization, Time Complexity of this is essentially $\mathcal{O}(n)$
- Using Matrix Exponentiation, this they claim is $\mathcal{O}(\log n)$
- Solving Recurrence to get a Formula [often called as Binet's Formula].
$$F_n=\frac{1}{\sqrt{5}}\bigg[{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n}\bigg]$$
Now, will the Time Complexity using this formula be $\mathcal{O}(1)$?
TL;DR: The three inter-related question are formatted using Bold. Since, the question is more of a convention, all relevant links are attached.