1

While I was reading the book 'Introduction to Algorithms by CLRS', I came across the sentence:

...is equal to g(n) to within a constant factor.

I've seen something about it in Merriam-Webster, but 'to within' is not clear to me, as I am not a native English speaker. Can anyone explain it to me?

  • Math question, not English language. Also this post is replete with typos, which makes it hard to tell what the question really is. – Xanne Jul 19 '17 at 2:20
  • @xanne what does merriam webster telling about it? – Noman Jul 19 '17 at 2:23
  • Well, Norman, what do you think it means? Why doesn't MW answer your question? – Xanne Jul 19 '17 at 2:25
  • •drove to within 50 yards of the green -- M-W example about golf. That means the golf ball landed less than 50 yards from the green. •worked hard to within five minutes of closing time -- M-W example. means that if closing time was 5:00 pm, he worked hard until 4:55 pm or a bit later. – ab2 Jul 19 '17 at 2:34
  • 2
    Wrong forum for this but Ill help. That section of the book is talking about growth order. In Big O notation we drop the leading coefficients + constants (they are insignificant for growth functions). Big O, Theta and Omega are just generalizations of how an algorithm will perform (within upper & lower bounds). So an algorithm that is ax2+bn+c is O(n2) for example. It means that the upper bound of the algorithm is no worse than n squared for some constant input factor "n". The algorithm will never perform worse than n squared for some value of n. Check ELL site. Talk to your prof. – Kace36 Jul 19 '17 at 5:10
3

Perhaps a non-math illustration will help clarify the meaning of "to within."

"The bullet penetrated his abdomen to within 1 cm of his spine." It describes that the bullet penetrated the abdomen and came to rest 1 cm or less distance from the spine.

"The home-made rocket climbed to within 5 miles of the stratosphere." This means the rocket climbed from the surface of the earth up to an altitude that is 5 miles from the stratosphere, up to but not including the stratosphere. So we don't know exactly how high the rocket went but its somewhere "within" that range.

2

Within refers to a margin of error. It is equal to g(n) plus or minus some constant factor. In math terms, g(n) = x +/- constant factor.

  • 3
    I would suggest correcting all three of these sentences. It's not a margin of error but a set of bounds; it's not addition but multiplication (note the term factor); it's the value of something else that's being expressed in terms of a constant factor of g(n), not g(n) that's having its own value affected. – Mathieu K. Jul 19 '17 at 15:50
2

A is B to within a constant factor

means

A is between (B times a constant) and (B times a constant) where the first constant and the second constant are not necessarily the same.


Context:

From page 45 of the third edition (Cormen, Thomas H., et al. Introduction to Algorithms, MIT Press, 2014--via ProQuest Ebook Central):

Figure 3.1(a) from page 45 of Cormen, Thomas H., et al. Introduction to Algorithms, MIT Press, 2014

Figure 3.1(a) gives an intuitive picture of functions f(n) and g(n), where f(n) = Θ(g(n)). For all values of n at and to the right of n0, the value of f(n) lies at or above c1g(n) and at or below c2g(n). In other words, for all n ≥ n0, the function f(n) is equal to g(n) to within a constant factor.


The key is in

the value of f(n) lies at or above c1g(n) and at or below c2g(n)

where c1 and c2 are defined by the caption of Figure 3.1 as being positive constants.

So we can rephrase as

the value of f(n) is greater than or equal to a constant value times g(n) and less than or equal to a constant value times g(n).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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