Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). More formally it means there are positive constants c and k, such that 0 <= f(n) <= cg(n) for all n >= k. The values of c and k must be fixed for the function f and must not depend on n.

• O(n) - As the data doubles in size, the algorithm takes twice as long to run.
• O(n²) - As the data doubles in size, the algorithm takes four times as long to run.
• O(n³) - As the data doubles in size, the algorithm takes eight times as long to run.
• O(log n) - As the data size increases, the amount of time the algorithm takes to run increases, but increases less and less as the size increases more and more.
• O(eⁿ) - As the data size increases, the amount of time the algorithm takes to run increases exponentially, becoming very long very quickly.

As a former bookseller and math student, I want to second your nomination of Introduction to Algorithms--I wish my copy weren't hundreds of miles away--and also want to quibble with what you said about O(f(n)).

It is math.¹

A lot of interesting math--especially math of interest to computing science--is done through approximation rather than turning out exact answers. I, too, used to look down on that as not real math, but I was wrong.

Now that that's out of my system, here's a little more good advice from my bookseller self:

Don't buy a current used textbook. Instead, look for an old edition. Trust me on this--little has changed in calculus and trig in the last century or so--and old texts are worthless to the college bookstore. If they have any, they probably have them out on the dollar a sack sale table.

If they don't have them out there, ask the textbook manager or try a used non-textbook store, and don't pay over five bucks--ten at the most--or ask around for a freebie at the math department at the local colleges.

There is a very good chance that your math teacher can't help you--mine couldn't (but he was a good track coach, I'm told), when I took on calculus in tenth grade. What he did do for me (since he couldn't explain how the Chain Rule was derived) was tell me that if I'd sit in class and quietly study calculus, he'd grade me just on my text scores (i.e., no algebra homework). That I wasn't supposed to bug him with calculus questions went unsaid.

This doesn't mean that your teacher won't be able to help you directly with the material--more likely she can than can't, but it's not a slam dunk--but it does mean that she can surely help you in some manner. However, the degree of help you get in this optional exercise is more than directly proportional to the politeness and respect with which you approach her. Only a saint (and I've benefited from a couple) will help a hateful student.

Let's see, what else? Oh, yeah--for an introductory text on discrete math, I like Discrete Mathematics by Richard Johnsonbaugh. It's in its fourth edition, so look for an old edition, and again, don't go over ten bucks.

Good luck, and have fun!

adamsj

They laughed at Joan of Arc, but she went right ahead and built it. --Gracie Allen

---

1. I'm jealous of tadman, since, while I would agree with him that the ideas in the various O-notations are simpler than the ideas in multi-variable calculus, I found them harder to learn and prove.

Thank You! I find myself in the exact same category as the poster, I'm in high school, and have trouble with all this calculous. I looked at Discrete Mathematics, and it's perfect, designed for an introductory book. I'm just finishing up Knuth's The Art of Computer Programming, and once I read Discrete Mathematics I'll go back and reread Knuth's books; mabey I'll finally understand the math sections! Again, thanks.

The 15 year old, freshman programmer,
Stephen Rawls

Eh, I'll add my $.02 (hehe).
I think that the best math in computer science is the REALLY "outlandish" stuff, that you'll NEVER see in other fields. I love toying with Automata and Computation Theory problems. Nothing like a Turing Machine to make your day complete. And that is as MATHY as it gets, though it certainly doesn't feel like math was in high school, I didn't love math so much in HS... Not because of the teachers and all, but because I was taking the area of triangles just a bit more often than I care to think of.

Just Another Perl Backpacker

During my quest, I found a number of texts that were immensely useful, but I also found some resources on the web that I put directly to use.

These include:

• The e-Calculus Home page which has some great PDF tutorials
• Explore Math
• Probability.Net for Probability and Stats

I hope this helps. Good Luck.

C-.

I hope this could be useful. Have a good time :)

The most important thing is that you have a really solid understanding of geometry. My favorite tool for learning Euclidean geometry really well is a commercial Windows program called The Geometer's Sketchpad. Add-on modules for the sketchpad include trigonometry, so this might be a great way to learn it.

For calculus, there are many books to choose from. A solid, modern calculus textbook is Thomas' Calculus. Buy it used! This, combined with a Schaums Outline, is an unstopable combination. Thomas is both loved and hated by students and faculty all over, so don't be surprised if there are flames on this one.

If you have trouble finding a book that really suits you, extreme measures are called for. It turns out that there was a 'golden age' for textbooks. Books were written clearly and there was no worry about conforming to the latest educational fads. These years were from about 1958 to 1964. These books were written to win the space race. Many of these books can now be found for cheap at used book stores. The best bookstore for books from this period is Powell's Used Books.

If you have trouble affording the books you need, buy a used book. Also, you may want to buy additional, low cost books to fill in the gaps for your main text. This is especially important if you are teaching yourself, because there will be sections of your textbook that won't make sense. An explanation from another book may be all that you need to make everything clear.

A publisher that specializes in supplementary reading and problems is Schaums. You need Schaum's Outline of Theory and Problems of Differential and Integral Calculus and Schaum's outline of theory and problems of college mathematics: algebra, discrete mathematics, trigonometry, geometry, introduction to caculus.

A publisher that specializes in low-cost books is Dover. I don't recommend a Dover book as a main text. Instead, find a specialized Dover books that cover something that is interesting and uses the advanced math you are learning.

It should work perfectly the first time! - toma

Older editions of Thomas' Calculus had a really neat appendix called "Lies that your Computer and Calculator Told You", and it had a bunch of examples showing how to break, confuse or at least horribly slow down a lot of computational methods for some mathematical problems.

The point? Computers can never 'replace' math. They make things easier, but aren't a do-all end-all solution.

For example, try to use a TI-85 to find the derivative of the absolute value of x at x=0. The calculator tells you the answer is 0, when really it is undefined.

Sadly, that appendix seems to have disappeared from the newest edition (I could be wrong there).

Yes, yes, yes! to your suggestion of Thomas' Calculus book--it's so good, they actually reprinted the third edition as a classic. I have an alternate fourth edition, which is slightly more abstract in its approach, but still great.

I didn't really get calculus until I stumbled on the third edition in the town library--I'd tried many others, but that one really clicked for me. If I'd only found that one in ninth grade!

adamsj

They laughed at Joan of Arc, but she went right ahead and built it. --Gracie Allen

I'll second the advice that you seek advice from a teacher whom you regard as competent to get started. A high school is pretty likely to have extra books sitting around and it's pretty likely that you can borrow one. If not, they're often available at libraries and so on. There is such a glut of books available at that level that it's hard to know about any one in particular, and my experiences are too far behind me to remember. :-)

Perhaps even more important is that you find someone (perhaps the aforementioned hypothetical teacher; if that can't be done, sensible questions usually seem to at least receive hints on sci.math, although one has to cut through a lot of dross there too) who can give you some guidance while you study. It's all too easy to become distracted and miss the really important concepts. (A well written book should help ameliorate this effect, but it's always something for which to guard.) And while it best to work out as much as possible by oneself (IMHO), it's also silly to get stuck on and become frustrated by something that could easily be cleared up by spending a few moments with someone knowledgable.

Don't forget to do a lot of exercises, too. :-)

School bokks are slow advancing - they are spoon-feeding you. In city library, they might have popular-science books which might be much better suited for self-learner. Or some home-schooling books. Ask your teacher - if it is not too late.

From my own experience: I learned by myself over the summer 3 years worth of high-school math after my freshman HS year - I just borrowed the books from teacher. It is doable.

But knowledge of calculus did not helped me a lot in programming: It depends of your application, but you basicaly do not need advanced calculus. In 15 years of programming, I am using always integer numbers (or fixed decimal point, basicaly the same). I consider algebra much more usefull, and solving small little funny problems (like in Gardner books) much more relevant to programming (= solving problems) than knowledge of calculus.

I had a friend, PhD in astronomy, who told me he needs a week to switch from math (scientific) way of thinking (solving advanced differential and integral equations) to programming thinking (when coding huge FORTRAN program to calculate satelite trajectories).

Your mileage may vary - it depends on application.

pmas

To make errors is human. But to make million errors per second, you need a computer.