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


    • Program: IT

  • Niclas Alexandersson

    • 920203-0111


    • Program: IT

a) Problem size

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

b) Algorithm

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.

c) Runtime bound

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 .