Fog Creek Software
Discussion Board




Asymptotic Analysis

How important is asymptotic analysis in real coding life?

My university course doesn't cover this although I'm studing BSc CompSci but how important is it really?

If it's really THAT important I will make an effor to go through Big Oh notation etc but it seems that most programmers never use this at all. I'm not planning to go into hardcore algorithm design so can I just ignore this?

CompSci Student
Monday, August 05, 2002

In my opinion, you should definitely know what the O-notation means and how to use it. For example, you should be familiar with the complexity of common algorithms for searching and sorting. It's basic stuff.

Frederik Slijkerman
Monday, August 05, 2002


It's also really easy.  If you think it's hard, you're probably looking at it the wrong way.  Find someone who can explain it to you in simple terms, and then think "duh."

If you're finding it's a huge investment of your time, you're looking at it the wrong way.

Matt H.
Monday, August 05, 2002

Matt,

So far I've only seen examples with very formal mathematical proofs etc. Do you know where I can read up on it (links?) without having to buy yet another expensive texbook?

Thanks

CompSci Student
Monday, August 05, 2002

You want to get good at eye-balling an algorithm and knowing its order statistic. The fancy mathematical proofs are good for weird algorithms with order statistics like O(n**1.59) or O(n**2.71). You won't encounter any of these in real life.

In real life, you can go a long way just by counting the number of nested loops. If an outer loop gets executed O(n) times and an inner loop gets executed O(n) times, then the whole thing is O*(n**2).

Once you're good at recognizing order statistics, then there are a few very simple rules of thumb for algorithm selection:

1. If it's O(2**n) or O(n!), forget it. Choose a different algorithm, unless you know for dead certain that n <= 10.

2. Nobody will ever notice a factor of (log n). That is, the difference between an O(n) algorithm and an O(n log n) algorithm will not be perceptible to your customers. (Same for O(1) vs O(log n).) Choose the one that's easier to implement and maintain.

3. If you're building a library routine that will be called for each member of some sort of collection, it had better be O(1) or O(log n).

4. If you're doing something to a whole collection, your algorithm had better be O(n) or O(n log n).

5. Only violate rules 3 and 4 if either you are absolutely certain that the collection is small, or you are absolutely certain that a human won't be twiddling his thumbs waiting for an answer. (Even then, do a good job of estimating how long it will take.)

6. If you know that n will never exceed 10, don't even think about order statistics. Do whatever is easiest.

7. In many cases, your complexity is determined by the quality of the collection classes you use. Using a standard library will almost always get you a reasonable value compared to rolling your own.

Jim Lyon
Monday, August 05, 2002

1. Big O is important when you have to estimate run-time.

2. http://www.amazon.com/exec/obidos/ASIN/0262032937/qid=1028607461/sr=2-1/ref=sr_2_1/103-3169017-9801425

This is THE BOOK for algorithms, if u even want to buy one.

3. google this "Big O notation"

Prakash S
Tuesday, August 06, 2002

Did you take the "intro to data structure" course yet?

The basics should be in that course and that course should be compulsory. So don't worry. You know, there must be a course talking about why and how quicksort is better than bubble sort, or when is a linked list better than an array, etc..

The textbook I used was _Data structures, algorithms & software principles in C_ by Standish. In chapter 6, the author tells you everything you really need to know in less than 50 pages.

Sam Wong
Tuesday, August 06, 2002

The intro to Data Structures course I took was taught by a PhD comp sci student who had a BS and MS in Math and to him 'real world' was quantum mechanics. I gained nothing but confusion from his algorithm analysis sections of the course. my own study of this stuff proved more useful

No BS
Tuesday, August 06, 2002

Check out the web book:

Data Structures and Algorithms
with Object-Oriented Design Patterns

Not only does it have a good paragraph on Asymptotic Analysis, but also covers lots of algorythms to put it all into a practical context. 

Plenty of exposure to patterns, too.  Time well spent on all frounts.

Available in 3 flavours:

C++ : http://www.brpreiss.com/books/opus4/

Java : http://www.brpreiss.com/books/opus5/

C# : http://www.brpreiss.com/books/opus6/

Ged Byrne
Tuesday, August 06, 2002

Sam,

I'm gonna take the data structures module next semester. It's not compulsory anymore for some reason though.

However, Bog-Oh notation isn't covered though (I've seen last year's notes). It's mainly about how to do tree traversal and stuff like that - it does introduce all the main data structures though.

thanks for all your replies.

CompSci Student
Wednesday, August 07, 2002

-------------------------------------------------------------------
It's not compulsory anymore for some reason though.

---------------------------------------------  CompSciStudent

I think the theory is that a programmer doesn't need to know them anymore.

The Java and .Net apis have all the data structures you'll ever need.

Unless you want to be a system programmer, you can get away with never knowing them.

Sad but true.

Ged Byrne
Wednesday, August 07, 2002

But if you don't know the data structures, Ged, you can't know when to use them. I don't mean you should have to be able to code each and every one (as you suggest, maybe not even one of them), but you should at least be aware when you should use a tree as opposed a list (for example), and why.

2 euro cents
Wednesday, August 07, 2002

Does either library have a decent set of Graph/Network implementations?

Mr. Rhetoric
Wednesday, August 07, 2002

2 euro cents,

Totally agree with you.

You don't have to go far to see people using the API incorrectly.

The other thing is poor optimisation.  Big O gives you a method for systematically deciding which method gives the best performance in which circumstances.

Instead, optimisations are based upon superstition and clever tricks, which actually lower performance instead of increasing it.

Ged Byrne
Wednesday, August 07, 2002

*  Recent Topics

*  Fog Creek Home