Big O notation

[overwraith]

Have any of you ever done big O notation? I found some websites that describe it, but not many professional ones. Are there any books that describe it too?

[Teme64]

I think almost every computer science book has it. Especially books about algorithms. You could try to find some online course material about algorithms. Check also Wikipedia.

HTH

[Teme64]

Wikipedia had a really professional explanation about ordo i.e. I didn't understand the math :) But check the references and external links which this article has.

[cgeier]

Also search for "data structures" or "data structures and algorithms". Here's a url that showed up: https://www.cs.auckland.ac.nz/~jmor159/PLDS210/searching.html

[overwraith]

Ok, thanks. None of the school cirriculum books I have read broach the topic. I heard it mentioned in a C class but never substantially. I have had some Calculus classes, so I will understand some of the math, but honestly people just don't know how to teach math these days. From what I understand as a variable approaches infinity the algorithim will tend to reflect some of the features of a certain function, some terms will be dropped, and some will become more dominant. So algorithims can be evaluated for efficiency by attributing certain functions to them.

[Teme64]

a variable approaches infinity

You're right and that 'variable' is the number of elements. For example sorting algorithms are a well studied area of algorithms. Given N elements to sort, Bubble sort is an O(N x N) algorithm while Quick sort is an O(N x log(N)) algorithm.

some terms will be dropped

Ordo notation removes any constant factor from the algorithm. For example you could have an algorithm which takes 3xN operations and second algorithm which takes 70xN operations for N elements. Former algorithm would be more efficient in practise but in theory both are O(N) algorithms i.e. equally 'efficient' theoretically.

HTH

[sepp2k]

You're right and that 'variable' is the number of elements.

That variable is whatever you say it is. In the context of computer science it's usually the size of the input, but it could be anything as long as you make that clear. For example it's very common to express the complexity of graph algorithm in terms of two separate variables: the number of nodes and the number of edges.

Ordo notation removes any constant factor from the algorithm.

As well as constant summands, but that's not all. For example 3x^2+2x+1 is in O(x^2), so you don't just drop the constant factors and summands, you also drop any term t such that the limit of t/f(x) is 0.

Of course the function you're trying to classify may not be a simple sum of terms at all, so the dropping-constants-and-smaller-terms approach is just a rule of thumb.