pow(p, k):
product <- 1
for i in 1..k:
product <- mul(product, p)
return product
For this algorithm, if we use the input itself to calculate the running time, we get:
\[T(p, k) = \sum_{i=1}^{k}{\left[\floor{\log_2{p^{i-1}}} \cdot \floor{\log_2{p}} \right]}\]
Since multiplication is the elementary operation, declarations, assignments and return statements are not counted.
However, if we only know the length of the input, and not the numbers themselves, we get differing upper and lower bounds. A binary number of length \(n\) is any number \(k\) such that \(\floor{\log_2{k}}=n\). The smallest such number is \(2^n\), and the largest such number is \(2^{n+1}-1\). Let \(n=\floor{\log_2{k}}\) be the length of \(k\), and \(m=\floor{\log_2{p}}\) be the length of \(p\). We then get:
\[\begin{aligned} T_{\mathtt{min}}(m, n) &= \sum_{i=1}^{2^n}{\left[m^2(i - 1)\right]}\\ &= m^22^{n-1}\left(2^n - 1\right)\\ T_{\mathtt{max}}(m, n) &= \sum_{i=1}^{2^{n+1}-1}{\left[\floor{\log_2\big((2^{m+1}-1)^{i-1}\big)} \cdot \floor{\log_2\big(2^{m+1}-1\big)} \right]}\\ &< \sum_{i=1}^{2^{n+1}}{\left[ (m+1)^2(i-1) \right]}\\ &= (m+1)^22^{n}\left(2^{n+1} - 1\right)\end{aligned}\]
Looking at these bounds again in terms of \(p\) and \(k\), we get that:
\[\begin{aligned} T_{\mathtt{min}}(p, k) &= \floor{\log_2(p)}^2 2^{\floor{\log_2(k)}-1}\left(2^{\floor{\log_2(k)}} - 1\right)\\ &\geq \Big(\log_2(p)-1\Big)^2\frac{k}{2^2}\left(\frac{k}{2} - 1\right)\\ T_{\mathtt{max}}(p, k) &= \Big(\floor{\log_2(p)}+1\Big)^2 2^{\floor{\log_2(k)}}\left(2^{\floor{\log_2(k)}+1} - 1\right)\\ &\leq \Big(\log_2(p)+2\Big)^2 2k\left(2^2k - 1\right)\end{aligned}\]
This essentially means that the algorithm takes a polynomial amount of time with respect to the numeric values of \(p\) and \(k\), but exponential time with respect to the number of bits needed to represent them.