O'Reilly logo

Concrete Mathematics: A Foundation for Computer Science, Second Edition by Oren Patashnik, Donald E. Knuth, Ronald L. Graham

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

9. Asymptotics

Exact answers are great when we can find them; there’s something very satisfying about complete knowledge. But there’s also a time when approximations are in order. If we run into a sum or a recurrence whose solution doesn’t have a closed form (as far as we can tell), we still would like to know something about the answer; we don’t have to insist on all or nothing. And even if we do have a closed form, our knowledge might be imperfect, since we might not know how to compare it with other closed forms.

Uh oh . . . here comes that A-word.

For example, there is (apparently) no closed form for the sum

Image

But it is nice to know that

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required