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
To get access to this content you need the following product:
The assumption \(A(k) = \Omega (1)\) is valid provided the body of the loop contains at least one operation.
Dynamic allocation can fail if not enough memory is available. Thus it is good programming practice to test whether the allocation operation succeeded. In our C \(++\) code, however, we suppress almost all error-handling in order to avoid cluttering the code and obscuring the main ideas.
An Abstract Data Type (ADT) is a set of objects together with a set of operations, both of which are mathematical abstractions. In the definition of an ADT, there is no mention of how the operations are implemented.
- Deterministic Analysis of Algorithms
- Springer International Publishing
- Sequence number
- Chapter number
- Chapter 5