Swipe to navigate through the chapters of this book
This chapter introduces the core of the analysis of algorithms theory, explaining the concept of basic operation, followed by traditional loop counting, and the ideas of best case and worst case complexities for both execution time and required space. A detailed analysis is provided for the classes of algorithms involving most common data structures. This chapter compares several sorting algorithms and discusses the theorem setting the lower bound for the worst-case complexity of comparison-based sorting algorithms. It also discusses algorithms with unusual and interesting proofs of their complexity, such as Euclid’s algorithm or KMP for pattern matching.
Please log in to get access to this content
- Deterministic Analysis of Algorithms
- Springer International Publishing
- Sequence number
- Chapter number
- Chapter 5