The history of Algorithmic complexity

(ProQuest: denotes formulae omitted.)I. IntroductionComputers have changed our world. The exploding development of computational technology has brought algorithms into the spotlight and as a result, the analysis of algorithms has been gaining a lot of focus. An algorithm is a precise, systematic method for solving a class of problems. Algorithmic thinking, which is a form of mathematical thinking, refers to the thought processes associated with creating and analyzing algorithms. Both algorithms and algorithmic thinking are very powerful tools for problem solving and are considered to be key competences of students from primary to higher education (Capay and Magdin, 2013) An integral component of algorithmic thinking is the study of algorithmic complexity, which addresses the amount of resources necessary to execute an algorithm. Through analyzing the complexity of different algorithms, one can compare their efficiencies, their mathematical characteristics, and the speed at which they can be performed.The analysis of algorithmic complexity emerged as a scientific subject during the 1960's and has been quickly established as one of the most active fields of study. Today, algorithmic complexity theory addresses issues of contemporary concern including cryptography and data security, parallel computing, quantum computing, biological computing, circuit design, and the development of efficient algorithms (Homer and Selman, 2011) Lovasz (1996) writes "complexity, I believe, should play a central role in the study of a large variety of phenomena, from computers to genetics to brain research to statistical mechanics. In fact, these mathematical ideas and tools may prove as important in the life sciences as the tools of classical mathematics (calculus and algebra) have proved in physics and chemistry" (pg. 1).High School mathematics courses tend to be focused on preparing students for the study of calculus. Sylvia da Rosa (2004) claims that this has led students to the common misconception that mathematics is always continuous. In addition, few students are excited by pure mathematics. For most students to begin to appreciate mathematics, they have to see that it is useful. Incorporating the topic of algorithms in high school would afford teachers and students the opportunity to "apply the mathematics they know to solve problems arising in everyday life, society and the workplace" (CCSSI, 2010) Bernard Chazelle, a professor of computer science at Princeton University, in an interview in 2006 said on the future of computing: "The quantitative sciences of the 21st century such as proteomics and neurobiology, I predict, will place algorithms rather than formulas at their core. In a few decades we will have algorithms that will be considered as fundamental as, say, calculus is today."Although there have been papers and books written on the history of algorithms, the history of algorithmic complexity has not been given nearly as much attention (Chabert, 1999; Cormen, et al. 2001) This paper will address this need by providing a history of algorithmic complexity, beginning with the text of Ibn al majdi, a fourteenth century Egyptian astronomer, through the 21st century. In addition, this paper highlights the confusion surrounding big O notation as well as the contributions of a group of mathematicians whose work in computability theory and complexity measures was critical to the development of the field of algorithmic complexity and the development of the theory of NP Completeness (Knuth, 1976; Garey and Johnson, 1979) In effort to provide educators with context for which these topics can be presented, the problem of finding the maximum and minimum element in a sequence is introduced, along with an analysis of the complexity of two student generated algorithms.II. History of Algorithmic ComplexityHistorically, an interest in optimizing arithmetic algorithms can be traced back to the Middle Ages (Chabert, 1999)