Puzzle: Analysis of Algorithms
Programmers are sometimes given an algorithm and are asked to figure out complexity by looking at the code. But computer science textbooks rarely ask the opposite question: given a performance chart of a particular program, figure out something about the algorithm. So, to break this trend, I’m asking you, the reader, to look at the chart below and figure out something about the sorting algorithm which generates this complexity curve. What class of algorithms is being used and what are peculiarities of data?
Use the underlying data as your guide, next week will talk about analysis of the problem.