Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I read the following in Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne:

Our first qualitative observation about most programs is that there is a problem size that characterizes the difficulty of the computational task. Normaly, the problem size is either the size of the input or the value of a command-line argument. Intuitively, the running time should increase with problem size, but the question is by how much it increases...


Another qualitative observation for many programs is that the running time is relatively insensitive to the input itself; it depends primarily on the problem size. If this relationship does not hold, we need to take steps to better understand and perhaps better control the runnig time's sensitivity to the input. But it does ofter hold, so we now focus on the goal of better quantifying the relationship between problem size and running time

My question is, if the input size (problem size of the program) increases, and thus the running time also increases, why would the running time of the program be relatively insensitive to the input? I'm confused.

share|improve this question
up vote 6 down vote accepted

I think they're not trying to say that the running time doesn't depend on the input size, but rather that it's relatively unlikely to change if you use different inputs of the same size.

For example, a program which inputs n different numbers and calculates the sum of those numbers probably has linear running time, but it shouldn't matter much whether the n numbers are all 0's or some of them are larger than 100 etc.

share|improve this answer
I agree. Some algorithms are very insensitive to initial conditions (summing); others are very sensitive (bubble sort). If you're in the latter case, then big-O notation isn't as useful. – Alex Feinman Aug 15 '12 at 14:31
+1 Thanks, I understand now. I think I read those qualitative observations too literally – Anthony Aug 15 '12 at 14:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.