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!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: