15

Examples Of Complexity Calculation

Objectives

After reading this chapter, you should understand:

  • How to determine the Time Complexity of Sorting Algorithms
  • How to determine the Time Complexity of Set Operations and Mappings
  • The Binary Search Principle
  • Application of Bit Vectors: Analysis of Hashing, The Trie Principle
  • Amortized Analysis: Principles and Applications
  • Potential Functions
  • How choice of Data Structure affects Complexity
  • The Binomial, Binary and Fibonacci Heaps: Working, Applications and Implications for efficiency
  • Time Complexity of Dijkstra’s Algorithm: Influence of Data Structure
  • Splay Trees: Principles, Organization, Analysis and Applications

If a thing is worth doing, it’s worth doing well — unless doing it well takes ...

Get Design and analysis of Algorithms, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.