Does anyone out there have an easy to understand explanation of big O. I will need to be able to look at a for loop, sort or other control structure and tell if it is quadratic, O(n), O(n^2), O(n Log n). I have looked in several of my refrence books, and they all make it seem so confusing. Is it really this hard to understand? I am new to C++, so any advice helps. Thanks!

Yes it is a pain to understand. However, you may enjoy this little loophole... If you look at an algorithm and have to say whether it is O(n), O(nlgn) or O(n^2), you are ALWAYS correct if you say O(n^2). Why? Because big-O notation is an upper bound on the time or space complexity, and since O(n^2) is the largest of the three, if O(nlgn) or O(n) is an upper bound, then O(n^2) is an upper bound as well. (O(n^2)>O(n) or O(nlgn)). I bet if you could argue it properly, you could answer O(n^2) to all of them and get full credit. Theta notation is what should be used for these kinds of questions. It implies a "tight" bound. Anyhow, assuming you don't want to use my little loophole, I'll give it a go to explain big O. I'll purposely leave out the mathematical notation, although it's worth going through, and show a few programming examples instead, since this is what you'll have to do. Here is a loop that adds two to each member of an array  of n numbers for (int i=0; i<n; i++) {    a[i]=a[i]+2 } As you can see, this loop will execute once for each  number in the array, or n times.  So removing any constants  of execution (like the time it takes to perform the  addition) you get O(n) is an upper bound on the execution  time.  This is pretty easy. Here's one for O(n^2) - This loop will sort an array  of n numbers.  O(n^2) algorithms usually involve nested  loops: for (int i=0; i<n; i++) {     while (a[i]>a[i+1])     {         swap (a[i],a[i+1])     } } I have no idea if this actually works, I haven't thought  about it, but it's easy to see that each number could  potentially be compared to each other number n times.   n*n=n^2.  So again, you neglect the time it takes  to execute the loop and do the swap, and you see that  this loop would not make more than n^2 comparisons,  so we say it executes in at most O(n^2) time. Now for the hardest one, O(n lg n)  This usually occurs  in algorithms where you're cutting something in half  each time.  They often involve recursion (a function  calling itself), only you call it with half the amount  of data each time.  I can't think of any small enough  examples of this, so I'll leave that open to anybody  else.  Quicksort, heap sort, and merge sort are two  nlgn algorithms well documented on the web. Let me reemphasize, with any of the above cases, I  could have just said they're all O(n^5) or something,  because we're talking about upper bounds. Hope this helps,  I wrote a lot because I had a tough  time with this in school and wish somebody had explained  it to me.   -SN

So, would it be safe to say, that for simple loops it would be O(n)? And for nested loops it is O(n^2)? (what would a triple loop be? Still O(n^2)?)I realize that last one may seem ignorant, but I am a newbie. *BTW are these best case or worst case senerios? And last but not least, if you can identify any routine as doing a heap, merge, quick sorts, it is going to be O(nlogn). Would I be safe for assuming this for worst, average and best case senerios? Also, I like that loop hole. I think I will memorize it just incase i have it as a written test question about a sort or somthing. Thanks!

Big O is a big pain. But SN did a good job explaining, except I wouldn't try the O(n^2) arguement on a test. It would be technically correct, but not the answer they want. One for statement O(n) two nested for statements O(n^2) three nested for statements O(n^3)... Best case and worst case are usually included in sorts that check if the list is sorted. Like in a bubble sort, you'd set changes=false, then if a swap was made, changes=true. When a loop completes with changes=false, stop. So if the list was completely sorted, you'd go through the list once, or O(n). Worst case, compare n items n times. Or O(n^2). The average would still be O(n^2) because if the list was half sorted, N/2 * N/2 = (N^2)/4 or O(N^2).

Chase is right on the nested loops increasing the exponent...Three nested loops (assuming each loop goes through some fraction of the n elements) would be O(n^3), and so on. Teachers are usually careful about how they phrase the questions, so be careful on the loophole. I think you may have misunderstood it. O(n^2) is always a correct answer only if you are choosing from the three you mentioned. It's possible to have O(n^3) on up, so O(n^2) would be an incorrect answer if the algorithm can run in O(n^3) or worse. However, I'm a scrapper, I fight for every point I think I deserve, and I think most teachers would give it to you if you really fought for it. You're better off actually learning the material though:-) If I remember correctly, a worst case of quick sort can actually be O(n^2), but on average it will beat heapsort or merge sort. I probably shouldn't have included it in the O(n lg n) group. Both heapsort and merge sort have slightly better "best case" scenarios, they might get down to O(n), but I'm not sure. So to answer your question, if you recognize an algorithm to be heap or merge sort, you can jot down O(n lg n) and move on to the next question. If you recognize it as quicksort, write O(n^2), and if they mark you down for it, whine and complain until they give you the points for getting the "technically" correct answer. Insertion sort, similar to the second example in my first post, runs in O(n^2) time, but for small inputs is significantly faster than any of the others. This is because there is very little overhead with swapping (as opposed to partitioning, heapifying, and merging as you have to do in the other algorithms) Big-O usually refers to worst case scenario, there are other measurements for best and average, so you probably won't have to worry about that. I'm sure you can find more exact answers on the web. Who cares about best case, anyways? Good luck, -SN

Thanks all... I think I understand the basics. The math part will have to wait until later. We(my class) have just been introduced to Big O. This is C++ II class and deeper exploration will come in the next C++ class. Thanks again!

SN - I'm impressed. All I remember about this stuff is that I must have slept during the time that we discussed it in my Algorithms class. My question is, have you, as a person who understands this, ever used it outside of the classroom. I know that in the nearly 20 years since college (cough*old*cough*fart*cough), I've never had a situation where I or anyone that I know used this stuff. But that could be because I wouldn't be able to if my life depended up on it!!!