I'm trying to improve my skills in analysis of algorithms. I think Sedgewick's "introduction to the analysis of algorithm" is a good, I'm reading carefully the first chapter, at least I'm trying. And the following is mentioned:

The first, popularized by Aho, Hopcroft, and Ullman and Cormen, Leiserson, Rivest, and Stein, concentrates on determining the growth of the worst-case performance of the algorithm (an “upper bound”). A prime goal in such analyses is to determine which algorithms are optimal in the sense that a matching “lower bound” can be proved on the worst-case performance of any algorithm for the same problem. We use the term theory of algorithms to refer to this type of analysis.

Which explains the approach adopted in CLRS

It is also mentioned

The second approach to the analysis of algorithms, popularized by Knuth, concentrates on precise characterizations of the bestcase, worst-case, and average-case performance of algorithms, using a methodology that can be refined to produce increasingly precise answers when desired. A prime goal in such analyses is to be able to accurately predict the performance characteristics of particular algorithms when run on particular computers, in order to be able to predict resource usage, set parameters, and compare algorithms. This approach is scientific: we build mathematical models to describe the performance of real-world algorithm implementations, then use these models to develop hypotheses that we validate through experimentation.

So this is the approach adopted by Knuth (I guess the analysis in "The art of computer programming" follow such approach).

I do get the general idea of course, but not the application, is there a specific application of these concepts you can point out? For example I do know the CLRS analysis of quicksort for example, how would this be any different from a scientific approach?

  • 1
    $\begingroup$ Sure. Try reading each of those books. They have many examples of that style of analysis. $\endgroup$
    – D.W.
    Mar 30 '18 at 0:24
  • $\begingroup$ You can also see Sedgewick's lectures on Coursera. Basically, the “theory of algorithms” approach (as in AHU / CLRS) is to analyze only the worst case, and to only care about the rate of growth, not the constant factor. Sedgewick has examples (using mergesort) of how the methods differ; just read further in the chapter or watch the videos/slides. $\endgroup$ Apr 5 '18 at 2:55
  • $\begingroup$ @ShreevatsaR that's one of the things, worst case to me is related to $O(\cdot)$ notation. However CLRS defines and use also $\Omega(\cdot),\Theta(\cdot)$, which model some how best case as well, the $\Theta(\cdot)$ models both somehow. I really can't read the TAOCP for now, because the exposition the author provides about sorting algorithm is a bit unusual to me. $\endgroup$ Apr 5 '18 at 8:24
  • $\begingroup$ For TAOCP I'm not talking about the analysis, but the actual exposition of the pseuducode of the algorithm, mergesort for example is a bit unreadable to me. $\endgroup$ Apr 5 '18 at 8:25
  • $\begingroup$ You don't have to read TAOCP, the "scientific approach" is well covered in the introductory chapters of the Sedgewick book using Java code. (BTW $O()$, $\Omega()$, $\Theta()$ as used in CLRS are about upper, lower and tight bounds all on the worst-case running time, they are not about worst-case, best-case, average-case.) $\endgroup$ Apr 5 '18 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.