authorea.com/7141

Algorithms - Lab 4, Problem 2

This is a hand-in written by **Group 7** (FIRE) for the Algorithms course (**TIN092**) at Chalmers University of Technology.

Group 7 consists of:

**Mazdak Farrokhzad**901011-0279

twingoow@gmail.com

Program: IT

**Niclas Alexandersson**920203-0111

nicale@student.chalmers.se

Program: IT

The size of the problem \(n\), as a function of \(p, k\) is: \[n(p, k) = \floor{\log_2{p}} + \floor{\log_2{k}}\]

```
pow(p, k):
product <- 1
for i in 1..k:
product <- mul(product, p)
return product
```

[H]

[1]

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.

As we saw above, the algorithm takes exponential time as a function of the size of \(k\), even if its behaviour can bee seen as polynomial with respect to the numeric value of \(k\). These kinds of algorithms belong in a complexity class called `pseudopolynomial complexity`

.

## Share on Social Media