News for hackers. Stuff that matters.
Re:A Gentle Introduction to Algorithm Complexity Analysis by hackermailman on Thursday June 14, 2018 @11:49AM (#17312527)
This Parallel & Sequential Algorithms book from CMU uses a simpler language cost model instead of the traditional machine based model to do analysis if anybody is interested http://www.parallel-algorithms-book.com/

When using a machine model, we have to reason about how the algorithm compiles and runs on that machine. For example, if we express our algorithm in a low-level language such as C, cost analysis based on a machine model that represents a von Neumanm machine is straightforward because there is an almost one-to-one mapping of statements in C to the instructions of such a machine. For higher-level languages, this becomes trickier. There may be uncertainties, for example, about the cost of automatic memory management, or the cost of dispatching in an object-oriented language. For parallel programs, cost analysis based on machine-based models even more tricky, since we have to reason about how parallel tasks of the algorithm are scheduled on the processors of the machine.

There are no comments on this comment yet.