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?
overwraith 83 Newbie Poster
Teme64 215 Veteran Poster
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
cgeier 187 Junior Poster
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 83 Newbie Poster
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 215 Veteran Poster
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 378 Practically a Master Poster
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.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.