I decided to take the algorithms and data structure course on coursera. I’m on week 1 right now and while I understand the concepts and the problems as well as the solution, but I’m having trouble understanding some of the math behind the conclusions they draw regarding algorithm performance and time complexity. E.g., I understand how union-find algorithms with weighted quick union work, but when they say that the depth of any node in the object is (lg N), I have no idea how they got to the expression lg N.
I guess it’s more of an intermediate course on algorithms so they expect you to know some Math coming in. Does anyone know of any good sources for learning math related to algorithms and data structures? Or just a brief list of the mathematics concepts that you are expected to know would also be great. Or if you know of a more suitable algorithm course, that would be great too.