OLYMPIADS IN INFORMATICS, 2017, Vol. 11, pp. 77 - 86
© IOI, Vilnius University
ISSN 1822-7732
DOI: 10.15388/ioi.2017.06
An Introduction to Running Time Analysis for an SOI Workshop
Dennis KOMM, Tobias KOHN
Department of Computer Science, ETH Zürich
Universitätstrasse 6, 8092 Zürich, Switzerland
e-mail: {dennis.komm,tobias.kohn}@inf.ethz.ch
Abstract
We organize an introductory course on algorithm design and complexity analysis for prospective participants of the Swiss Olympiad in Informatics and interested high school students. The students are assumed to have some background in programming, but no formal computer science education.
Our goal for the first lesson is to introduce them to the basic tools used in running time analysis, with a particular emphasis on worst-case versus best-case analysis, uniform versus logarithmic cost measurement, and big-O notation; however, we avoid being too formal and use the example of primality testing to introduce the concepts hands-on. In this paper, we describe our approach in detail.
Keywords:
SOI workshop, running time analysis, worst-case analysis, cost measurement, big-O notation
To preview full
article text in PDF format click here
You
could obtain free Acrobat Reader from Adobe
Copyright © International Olympiad in Informatics, 2017
Vilnius University, 2017