   Algorithm complexity
  HiI just bought a book about STL amd its talking about constant/linear/algorithmic complexity for many operations such as insertion, deletion etc.I'm not sure what that exactly means.- Linear complexity means o(n) right ? That is the more elements in your container, the longer the operation will take. Typically because the operation requires to access the container sequentially to find a particular position or element.- Logarithmic is o(log n) ? or o(n log n) ? I know that's for example the complexity of certain tree operations. For example inserting an element in a balanced binary of 2,000,000 elements tree requires just 1 more operation thant on a 1,000,000 tree (thats a very basic example of course)- Constant ? What exactly does constant means ? To me it sounds that it just is independant of the number of element, but that doesnt tell me if its always good or always bad.Just a little confused so if someone could take a few clear that up for me I would really appreciate :)CheersJanta, who at last decided to use STL :P but want to use it cleverly.   
  Big-O notation is a very important skill to learn for computer science and will help you understand how to compare algorithms regardless of machine speed and data types.Quote:Original post by jantaHiI just bought a book about STL amd its talking about constant/linear/algorithmic complexity for many operations such as insertion, deletion etc.I'm not sure what that exactly means.- Linear complexity means o(n) right ? That is the more elements in your container, the longer the operation will take. Typically because the operation requires to access the container sequentially to find a particular position or element.Yes. Linear complexity grows linearly (the graph of time vs. number of elements is a straight line). An example would be the "dumb" search of a 1D array, where if it takes one second to search an element, it will take five seconds to search five elements.Note here that O(n) is a class of algorithms; this only rates how it scales. It may take 2 seconds for the first and last elements, for example.Quote:- Logarithmic is o(log n) ? or o(n log n) ? I know that's for example the complexity of certain tree operations. For example inserting an element in a balanced binary of 2,000,000 elements tree requires just 1 more operation thant on a 1,000,000 tree (thats a very basic example of course)Not always that extreme, but it's in the "class" of logarithmic operations (the graph makes a logarithmic pattern). An example would be a tree traversal.Quote:- Constant ? What exactly does constant means ? To me it sounds that it just is independant of the number of element, but that doesnt tell me if its always good or always bad.Constant (O(1)) takes the same amount of time regardless of how many elements you are processing. That is almost always good, unless that amount of time is more than you would spend on a different algorithm. An example of a constant operation would be adding one number to another (generally).There are also classes of very inefficient algorithms -- you may have encountered O(n2) algorithms. These are generally much less efficient. You definitely want to avoid them as much as possible, and really avoid the exponential class of algorithms (e.g. O(2n)). These are algorithms such as the travelling salesman problem.Hope this helped! You may also wish to read the wikipedia entry on Big O.   ;  Linear means that the time taken for an operation grows, well, linearly with the size of input. Sorting 20 elements would take twice as long as sorting 10, assuming a linear sorting algorithm.Nastier algorithms may have O(n^2) or worse, O(2^n) (or any other exponential function). The former are usually still acceptable (but slow). But if you run into the latter case, it's time to switch off the computer and become a carpenter or something instead... [wink]But one thing to keep in mind is that big-O notation is "only" an abstraction.It doesn't tell you whether it's faster to use quicksort or mergesort on *your* particular list of 10000 elements.It tells you that *in the general case*, for sufficiently large input, one algorithm will sooner or later be faster than the other.What it means is basically that if you've got an O(lg n) and another O(n^2) algorithm, the O(n^2) algorithm will sooner or later become slower than the O(lg n) one, as input grows. That might happen when you pass the algorithm 3 numbers, or it might happen when you pass it 3 billion numbers. But it'll happen sooner or later. And from that point, and all the way to infinity, the O(lg n) algorithm will always be faster.Or in the case of constant time (O(1) complexity), it means that an operation takes a fixed amount of time, regardless of the size of input.That's usually a good thing, but if the constant time required is, say, one hour, it'll be slower than many O(n^2) algorithms for common input sizes. But if the input grows big enough, the non-constant algorithm will become slower. [wink]It's a handy notation for comparing algorithms and arguing about their efficiency. But it's not *accurate* (and isn't meant to be)   ;  Algorithmic complexity is useful for estimating how bad things will get if your "problem size" (amount of data to be processed) increases. Usually, you'll get better performance out of an algorithm with "better" complexity for any real-world problem, except when the problem size is small or the constants involved differ by a lot. It's also used in theorems, which in turn are useful for figuring out whether you're doing "well enough". For example, if you worked out that your comparison-based sorting algorithm runs in O(n lg n), you can take comfort in the fact that there exists a simple proof that you won't be able to trim that down to O(n), at least not without switching away from comparison-based sorting and towards something that "knows something about the data". (The proof goes roughly as follows: For n elements, there are N! possible orderings, which makes lg2(N!) bits of entropy. You need to get rid of all of that, because there's exactly one state you will accept - lg2(1), i.e. 0 bits of entropy. But because a comparison is a simple binary decision - swap the elements or don't - you can only remove O(1) bits with each comparison. Thus you need O(lg2(N!)) comparisons to finish in the worst case, which makes O(lg2(N!)) - which simplifies to O(N lg2 N) - total running time.) Sometimes, practical implementations of recursive algorithms (I should say divide-and-conquer algorithms; they don't necessarily have to be written recursively) will switch to a simple implementation for small problem sizes, even if the complexity ranks worse - exactly because the abstraction breaks down for small problem sizes. This usually does not change the order of complexity of the whole algorithm, if the threshold for "small size" is constant. (Informal proof: the time taken by the "slower" algorithm on the small sized problem is bounded by some constant - i.e. the amount taken for the full "threshold size" number of elements - and then you effectively have a divide-and-conquer algorithm applied to n/k elements, with a constant factor of c1(k), the ratio of max time taken by the small sized problem to the time otherwise taken for a single element. Meanwhile, F(n) / F(n/k) is typically bounded by k, and in more cases by some constant related to k.)This is done, for example, by the standard library implementation of std::sort: it switches to a bubble sort for small lists, and otherwise does quicksort or bubblesort to process the list recursively.   ;  Thanks for the clarification.So big O notation gives the algo's performance in an average case ? I thought it was in the worst case. Or are there also a Big O classification for a worst case ? I think of a binary tree for example, which element were inserted in increasing order. Wouldnt complexity switch from O(log2(n)) to O(n) ?JantaPS: sorry if this topic is not really appropriate in For Beginner. I always come up with more and more questions :P   ;  Well, if you want to get technical, Big-Oh is WORST case... it's an upper bound, but it is often used when referring to the average case informally.  The technical notation for the average case is Big Theta, and it is typically much more difficult to compute.   ;Quote:Original post by jantaI think of a binary tree for example, which element were inserted in increasing order. Wouldnt complexity switch from O(log2(n)) to O(n) ?Insertion/search in an unbalanced binary tree is O(n), because you could end up with a completely lopsided tree consisting, essentially, of a single linked list from the root to the leaf.  If it is balanced, traversal is an O(lg n) operation because you are able to reduce the search space to 1 / (branch factor) for each operation.   ;Quote:Original post by smitty1276Insertion/search in an unbalanced binary tree is O(n), because you could end up with a completely lopsided tree consisting, essentially, of a single linked list from the root to the leaf.  If it is balanced, traversal is an O(lg n) operation because you are able to reduce the search space to 1 / (branch factor) for each operation.Ok, but a binary tree is a binary tree right ? In a real world situation you dont know wheteher its elements were inserted sorted or not do you ? Is that why people usually assume that the tree is roughly balanced ? So I'd conclude that a inserting in a B-Tree is a O(log2 n) operation, which is in no way a guarantee for all tree, in particular if the tree ends up being a linked list.Am I right ?;Quote:Original post by jantaOk, but a binary tree is a binary tree right ? In a real world situation you dont know wheteher its elements were inserted sorted or not do you ? Is that why people usually assume that the tree is roughly balanced ?Some tree data structures do guarantee that the tree will be balanced. But yes, "plain" binary trees suffer from this weakness. You don't know if your tree is going to be balanced, so your worst-case times will suffer. And you don't usually want that. :)Quote:B-TreeB-Tree or binary tree? They're not the same... [grin]   ;Quote:Original post by jantaOk, but a binary tree is a binary tree right ? In a real world situation you dont know wheteher its elements were inserted sorted or not do you ? Is that why people usually assume that the tree is roughly balanced ?No.  People usually assume that the tree is roughly balanced because they use balanced trees... red-black trees are probably the most common.  That's definately what the Java types use and I think they are heavily used in STL as well.If you are using a vanilla binary tree, there is no guarantee that it is balanced unless you take precautions.  In fact, inserting elements that are presorted into a plain old binary tree without taking action to balance the tree will GUARANTEE that you have a perfectly linear arrangement of elements and will get the worst -- O(n) -- performance out of it.   