C# and Big-Oh notation

C# and Big-Oh notation

• R1ZWAN

  Big-OH notation is used in analyzing the performance of data structures.

  There is a good article on this subject on msdn. The link is as follows

  http://msdn.microsoft.com/library/default.asp url=/library/en-us/dnvs05/html/datastructures20_1.asp

  There are more articles that talk about data structures in C# along with examples.

  Aslo, look at http://mysite.verizon.net/msaleemyusuf/et601lect_1.htm

  there is a link to "Slides". It has information on this subject.

  Saleem

  
  

• Martin Koppmann

  I have been a professional programmer for over 20 years and I have never heard of Big-Oh before - my excuse is that I came into programming via cognitive science, and not computer science.

  At work we do a lot of profiling of our applications using load testing software like Silk Performer and Mecury LoadRunner. In the past I've also used TrueTime to profile code under single user conditions; even a stop watch is useful.

  After a while you hopefully get a feel for what is efficient code.

  I'm not saying your current studies are not useful/interesting, it is just in the real world, in my experience, a lot of the academic stuff is ignored for more pratical solutions (suck it and see).

  
  

• Beshr Kayali

  I have to admit that I don't know anything about code analysis tools. I'd doubt they could do big-Oh analysis, it requires the kind of computer you have between your ears to pull off tricks like that...
  
  
  
  

• macyp

  hello again dear developers,

  i have again a question...

  do existing code analyzer tools use such notation in their code analysis (aside from the cyclomatic complexities, LNOC, other metrics w/c are the usual approah in their analysis) if no, why do you think that this notation isn't included, are there any hindrances to the pratice of this approah in analysis

  
  
  

• Jay Burt

  thanks nobugz.

  hey dasa,

  since it's fundamental,so it should e taken into attention right

  "Or did you want to hear 'nah, nobody uses that stuff - drop that class' " ==> is this true though

  
  
  

• Pierre Leclerc

  A very important basic measure to determine what kind of algorithm you need to use to solve a problem. It gives you quick insight in how long code is going to run, based on the number of elements that are being processed. Rule of thumb: you'd never worry about O(n) or O(n*log(n)). Double nested loops are O(n^2), ok as long as n < 1000. Triple nested loops are O(n^3), ok as long as n < 100. A lot of real life problems are O(n!), always requiring a smart heuristic to have reasonable processing time while still getting reasonably close to the optimum solution.
  
  
  
  

• stswordman

  Big-O notation is "academic stuff" No way! It's fundamentally important to your choice of algorithm! If you don't know something about it now, you'd better get on to it!
  
  That is why Microsoft and others specify the complexity of fundamental algorithms such as searching and sorting algorithims using Big-O notation.
  
  For example, for ArrayList.Sort() the documentation states:
  

  "On average, this method is an O(n log n) operation, where n is Count; in the worst case it is an O(n^2) operation."

  And for List<T>.CopyTo() they say:
  
  "This method is an O(n) operation, where n is Count"
  
  And so on. It's VERY important to know these things.
  
  

• Michael Schreuder

  What I meant was, if the existing code analyzer TOOLS use this notation as an approach in their code analysis =)

  
  
  

• FedorSteeman

  It's fundamental since it is the basic vocab that succintly describes how an algorithm scales.

  Or did you want to hear "nah, nobody uses that stuff - drop that class" ;-)

  
  

• AKProgman

  That’s an np complete problem. You're smarter than a computer and can do a much better job of determining the big-O of an algorithm.

  Do we use big-O in our daily efforts Depends on what you do, but almost every database has log(n) algorithms at its heart.

  You may never use big-O, but it can sure make it easier to get the problem solved correctly the first time. Code profilers work, I’ve used them, but they’re no substitute for judicious use of an algorithm in the design phase. You can only patch something so many times before it becomes terribly difficult to patch again (unstable). It’s better if humpty never falls from the wall to begin with.

  So, if you understand big-O, it should make you a better programmer. If for no other reason, you understand what efficiency of algorithms means.

  BubbaB

  
  
  

• Siraj Ansari

  Thank you very much for your comments and really helpful explanations..=)

  Do code analyzers today use this notation as an approach in their code analysis

  
  
  

• mshvw

  I was being facetious. It is a basic notation that everyone in the field is expected to know. Even if you don't go much into data structure and algorithms, you should at least be able to read the notation so that you can select/make use of others' implentations by reading their documentation.

  To ShellShock:

  It's true that many of the stuff taught in CS curiculum doesn't apply in the industry setting. After all computer science (CS) is not software engineering (SE). But O() is a very basic notation that is as applicable to SE as much as CS, and, notwithstanding your experience, it is used commonly in the field.

  Regardless of the tools/methods you use to profile your code, once you got the numbers, you'd want to determine the causes of the performance characteristics, and adjust them for your needs. If you are not using O() notation, you're using some alternative vocabs to describe the characteristics, and they are likely less efficient (i.e. more verbose) and non-standard (i.e. more cumbersome when communicating with others).

  
  
• C# and Big-Oh notation