Techical Procedures

The basic idea is that you want a simple formula that converts the number of items you have to process to how long you can expect that to take. So, if you have 20 items and your Big-O is O(n^2), then it’ll take about 400 (of some unspecified unit of time/work) to process.

The actual number doesn’t matter, what matters is how quickly it grows as the number of items grows. Growing slower is better, of course. Because the actual number doesn’t matter, constants are discarded, and lower powers are discarded. O(2n^4 + 3n + 5) is just O(n^4).

Here’s how to roughly estimate the Big-O for your code:

Fixed work
Any random chunk of code that does something once (like, say, printing something to the screen, or initializing a variable) is O(1).

Binary search
If you hunt through the items using a binary search, where at each step you cut your search space in half, that’s O(log n). (That log there is base 2, not 10.) So, finding a number in a sorted array is O(log n). Most algorithms involving binary trees will have a “log” in their Big-O.

Loops
If you loop through all of the items, that’s O(n). So, finding the biggest value in an array of numbers (naïvely) is O(n).

Permutations
If you’re going through every permutation of your items, that’s O(n!). For example, if you’re doing a naïve algorithm to find anagrams using a given set of letters by trying every possible combination, you’re permutating.

Exponentials
The last common Big-O type is O(2^n). The only simple example I can think of is if you need to create a filled binary tree of depth n, then that’ll have O(2^n). There are some other algorithms that have this, but, thankfully, you shouldn’t run into it much.

So those are the basic types in order from best (fastest) to worst. Once you hit O(n!) or O(2^n), you’re in the range of algorithms where your code will very likely be too damn slow. This is why it’s good to know the Big-O of your code.

The question now is, how are these individual parts combined in a big chunk of code?

Sequential
If your code does one thing and then another, then the Big-O of those two parts are added. So, if you do some fixed work and then loop through your items, it’s O(1 + n). Since we discard any lower terms, what this really means is if you do one thing then another, take the bigger Big-O of the two (O(n) in our example).

Nesting
If your code does one thing inside another, then the Big-O of those two parts are multiplied. So, if you loop through all of the items and the loop through them again inside that loop, that’s O(n * n) or just O(n^2). This is the one you’ll need to pay attention to. If your code is calling some function within a loop that also loops through the items, you can end up with worse complexity than you realize.

Another example: if you iterate through each item in the list, and for each item, you do a binary search, that’s O(n * log n), or just O(n log n). Most sorting algorithms are around here. It’s better than O(n^2), but worse than O(n).

Recursion
This is a tricky one. If your code calls itself, it may be the same as nesting, or it could be better, or much worse. It all depends on your exit condition and how the input set is reduced at each recursive step. A recursive binary search only gives you O(log n) because each recursive call cuts n in half. If the recursion reduces the input size by only one each time, you’ve got O(n!).

A computer scientist would probably say this isn’t rigorous at all, but this should be good enough for an engineer. The goal here is to be able to quickly scan your code and get an idea of if it’s going to blow up and take forever or not.

Source: http://www.reddit.com/r/programming/comments/a940e/how_i_hire_programmers/c0gfm6g