Posted by hussein on July 12, 1999 at 08:14:41:
In Reply to: T(n) for Xmp 3.1 posted by Jeffrey_2Pi on July 12, 1999 at 00:12:18:
: When the author includes the time required for the assignment of a larger integer to curlarge in the constant c, is this because we are concerned with the worst-case scenario of a strictly increasing array where array[n+1] > array[n], for all n? Is that why
: T(n) != (c1)n + (c2) where c1 would be the time required to increment i, and c2 would be the time required to do the assignments?
the basic operation being counted is the comparison of integers ... and there are n such operations irrespective of whether we look at a best, worst or average case.
we cant count increments and assignments as separate terms in the same analysis because we dont know the relationship between these two operastions ... we have to define a "primitive" operation ... when the text refers to including the time for incrementing i, they are suggesting modifying the definition of their primitive operation.