Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm familiar with the basics of run-time analysis such as what makes certain types of code O(n) and O(n^2). But I'm having real trouble learning, understanding, and really remembering how to analyze pieces of code that run in other complexities such as O(n log n) or O(2^n). I'm looking for resources that explain in simple terms how these other complexities work and some practice problems to really force my understanding.

share|improve this question
add comment

2 Answers

I think the deeper issue here is algorithm analysis. It's easy to figure out what an algorithm's runtime complexity is if you know what's actually going on in the algorithm.

A book like Introduction to Algorithms will give you all the tools you need, and more than enough practice problems, and you should see the first answer here to get a great overview of the different runtimes.

Overall, however, practice makes perfect. When you multiply two numbers, you don't "remember" how multiplication works - you just multiply them because it's second nature. After you analyze enough algorithms, you being to understand what's really happening. You don't need to "remember" how algorithm analysis works - you just look at the algorithm, see what's happening, and you understand what's happening.

share|improve this answer
add comment

What works for me is to know a little bit of information theory. Specifically, when a program executes an IF statement like this:

if (test){
  ... code A ...
} else {
  ... code B ...
}

test has a certain probability P of being true, and 1-P of being false, and the information gained (into the program counter) when making that branch is I = log(1/P) (base 2).

If P is 0.5 (equally likely to be true as false), then I = log(2) = 1 no matter which branch is taken. That's the amount the program counter "learns" in making that choice.

Now Entropy (scary word, I know) is just average information gained over all branches, which is 1, right? So you could say that branch does 1 bit of work when it is executed.

Suppose P isn't 0.5. Suppose you are doing a linear search in a table of 1024 entries. The first test you do says "Is the 0th entry the one I'm looking for?". If the answer really could be anywhere, then P = 1/1024, and 1-P = 1023/1024.

So if the element you're looking for happens to be the first one, you gain log(1024) = ten bits, but if it isn't, you only gain log(1024/1023) or essentially zero bits. What's the entropy? It's the sum of the information you gain on each branch times the probability of that branch. It's 1/1024 * 10 + 1023/1024 * 0, which is about 1/102.4. That test "learns" less than 1-hundredth of a bit on average.

Since to find an element in a 1024-entry table, you need to learn 10 bits, you can see why linear search is slow. In fact, if N is the number of bits you need to learn, it's exponential!

That's why searches based on equally likely binary decision points are O(logN). A way to make a search faster than that is indexing. That's where you have an index and use it to locate an element of an array. If the array is 1024 elements long, that's like a decision point with 1024 outcomes. If they are all equally likely, what's the entropy? It's 1/1024 * log(1024) + 1/1024 * log(1024) ... for 1024 terms, which comes out to - ten bits. You learn all ten bits in a single operation!

OK, how about sorting? If you have N items, you need to search for where each one belongs in the array, so it basically costs N times the cost of the search. Couldn't be simpler.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.