Best resources to really understand run-time complexity [closed]

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.

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.

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.

Analyzing complex algorithms requires lot mathematical background. For a refresher on analysis of standard algorithms you can refer to books.

If you need a starting point for analysis of algorithms i would suggest to read some books on algorithms. The best book i can refer for analyzing algorithms is Introduction to Algorithms.

If you would like to attend lectures than reading there are plenty of videos on this subject. Such as MIT Lectures.

What you can try is to find the analytical expression that is equal to the cost of the algorithm you are working with.

In many cases, this expression might be a sum (usually for nested loops). However, for a recursive algorithm, you might express it's cost with a recursive formula that you will have to solve. For example, the cost of a binary search may be expressed with the formula T(n) = floor(T(n/2)) + 1 (worst case). By solving the formula we find that the answer is Θ(log(n)).

For sorting algorithms, we will usually have Θ(n^2) or Θ(n log(n)) average case (quicksort is Θ(n log(n)) average case but Θ(n^2) worst case!!). Sometimes the cost found by solving a recursive formula might even be exponential (see Tower of Hanoi problem), and that is something to worry about.

Finally, by using the Master Theorem when its possible, you can estimate the runtime complexity without explicitly solving the recursion, which is very useful.