An Introduction to Formal Languages and Automata, 7th Edition

14.1 EFFICIENCY OF COMPUTATION

Let us start with a concrete example. Given a list of one thousand integers, we want to sort them in some way, say in ascending order. Sorting is a simple problem but also one that is very fundamental in computer science. If we now ask the question, “How long will it take to do this task?” we see immediately that much more information is needed before we can answer it. Clearly, the number of items in the list plays an important role in how much time will be taken, but there are other factors. There is the question of what computer we use and how we write the program. Also, there are a number of sorting methods so that selection of the algorithm is important. There are probably a few more things you can think of ...