Mathematical basis for a fundamental tool in computer scienceMSc (Tech) Kalle Rutanen’s thesis provides a mathematical justification for the use of O-notation to simplify and to compare expressions used for describing the cost functions of programs.
When a computer is given a task, the time it takes to solve the task depends both on the efficiency of the computer and the efficiency of the program. The efficiency of the program is often much more important than the efficiency of the computer.
“Let’s say that we wish to rearrange n separate numbers into an ascending order. Program A, when run on a certain computer, uses n2 microseconds to perform the task, while program B, run on the same computer, uses 2n microseconds to perform the task. If there are 100 numbers to rearrange, program A completes the task in a hundredth of a second while program B completes the task in about 40 million billion years. Even if program B was performed by a computer which is a million times faster than the one used above, it would still take program B 40 billion years to complete the rearrangement. The difference would be even greater with a greater n,” says writer of the thesis, MSc (Tech) Kalle Rutanen.
In Rutanen’s example, the times to complete the programs were given in simple expressions, such as n2. In real-world programs, these expressions are more complex, such as n2 + 5n + 7.
“Since the term n2 still provides a good run-time estimate, computer scientists simplify this by saying that the program runs ‘in the order n2.’”
This simplification has been justified mathematically using a so-called O-notation, where the intuitive ‘order n2’ is replaced with the formal notation O(n2). However, it has not been clear how this O-notation should be defined for the task. Historically, computer science adopted the O-notation from mathematics. However, the concept of O-notation used in program analysis is different from the concept of O-notation used in mathematics.
“If the expression for the run-time is simplified at each step of the analysis, can you be sure that the end result is the same as when computing the run-time expression in exact terms and only simplifying the result afterwards?”
If the O-notation is adopted from mathematics, the answer to this question is ‘no.’
“One of my research findings was that there is exactly one definition for the O-notation that works correctly for program analysis. This definition does not correspond to the one used in mathematics,” Rutanen notes.
The rest of the thesis demonstrates that the O-notation and related theorems work as previously used.
Public defence of a doctoral dissertation on Saturday, 22 October 2016
MSc (Tech) Kalle Rutanen's doctoral dissertation in the field of mathematics entitled ‘O-notation in Algorithm Analysis' will be publicly examined at the Faculty of Natural Sciences of Tampere University of Technology (TUT) in room TB222 in the Tietotalo building (address: Korkeakoulunkatu 1, Tampere, Finland) at 12 noon on Saturday, 22 October 2016.
The opponents will be Professor Jarkko Kari (University of Turku, Finland) and Professor Pasi Fränti (University of Eastern Finland). Professor Sirkka-Liisa Eriksson from the Department of Mathematics at TUT will act as Chairman.
The dissertation is available online at: http://urn.fi/URN:ISBN:978-952-15-3841-4
Further information: Kalle Rutanen, email@example.com