CODEWITHSUNDEEP
algorithmsortingmath
Fabian
Fabian

Reputation: 191

Meaning of "constant factor of N"?

In a text I am reading (Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne) there is the following passage:

Increment sequences have been devised [for shellsort] that drive the asymptotic growth of the worst-case number of compares down to N^4/3, N^5/4, N^6/5, ... , but many of these results are primarily of academic interest because these functions are hard to distinguish from one another (and from a constant factor of N ) for practical values of N.

In this context what is the meaning of "constant factor of N"?

Upvotes: 2

Views: 709

Answers (2)

Alex Riley
Alex Riley

Reputation: 176938

The sequence N^4/3, N^5/4, N^6/5, ... approaches N because the exponent gets closer and closer to 1.

This means that the terms in "the asymptotic growth of the worst-case number of compares" get closer and closer to each other as N is approached. In practice, N can be treated as the constant factor.

(The author adds the caveat "for practical values of N" as, for huge values, the terms in the sequence will be distinguishable for longer.)

Upvotes: 2

Neithrik
Neithrik

Reputation: 2078

It would mean that the algorithm would take N time or N operations.

Author probably wanted to emphasized difference between N and O(N) time complexity in this case.

Upvotes: 1

Related Questions