Posted by: atri | December 14, 2011

## Clarification on the run time of an algorithm

I got an email from one of you and based on feedback from Jesse, looks like there is some confusion about the run time of an algorithms. So I’ll clarify that in this post– hopefully this clears away doubts that you might have. If not, please feel free to use the comments section.

As always, please do not try to read much into whether this is directly related to the content of the final exam. This seemed like a basic mis-understanding and I wanted to clarify it. As usual, make extrapolations at your own risk!

It has always been the case that the run time is measured in terms of the size of the input (say in bits). E.g., see slide 15 here. Thus, when one says a polynomial time algorithm, it is always in terms of of the input size. (I had mentioned this in the beginning of the semester and then I mostly neglected to mention this except when we were talking about Dijkstra’s algorithm I talked about the input size when the edge weights are arbitrary. Sorry for not stressing this enough.)

It has often been the case that the input size happens to be $\Theta(n)$, where $n$ is some natural parameter in the problem input– in most cases it has been the number of input items. Thus, in this case an algorithm whose running time is polynomial in $n$ indeed has a polynomial run time.

However, this is not always the case. Here are two examples:

• In the stable marriage problem, the input size is $\Theta(n^2)$, where $n$ is the number of men and women. Thus, the Gale- Shapely algorithm that runs in  $O(n^2)$ time is actually a linear-time algorithm.
• Another example is problem 2(a) in the sample final exam. In this problem, the input itself is a number is $n$ but the input size, which is the number of bits needed to represent the number $n$ is $\lceil \log{n}\rceil$, which is the input size.  (E.g., the input could be a number $2^{100}$, in which case the input size is $101$.) Hence, the algorithm presented in the problem has an exponential run time.

Hope this helps!