1
$\begingroup$

What is a good book or resource to find practical exercises of analysis of the complexity of concrete algorithm implementations (that is, which asymptotic complexity does a particular code have)?

I'm interested not in solving algorithms but in practising finding out their complexity. I have seen a couple of these kind of exercises in my Discrete Mathematics textbook (Rossen), but I haven't been able to find a good resource to find others.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Textbooks in algorithms are chock full with examples of algorithms, often with analysis. For example, take a look at Erickson's "Algorithms", Dasgupta et al "Algorithms". Looking around for lecture notes will get you a lot of others. Analysis of algorithms requires some specialized techniques, a modern overview is Sedgewick and Flajolet's "Introduction to the analysis of algorithms".

Improve this answer
$\endgroup$
2
  • $\begingroup$ thanks @vonbrand they are good resources. I was looking for something that provided just exercises together with their solutions, but I haven't found something like that. But these kind of books have exercises and some of them are, more or less, what I was looking for. I already know all these techniques but I want to practice them $\endgroup$
    – Emigre
    Commented Mar 18, 2020 at 17:13
  • $\begingroup$ I can also recommend "Generatingfunctionology" by Herbert S. Wilf which has many exercises on generating functions $\endgroup$
    – Emigre
    Commented Mar 18, 2020 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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