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   Fog Creek Home