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


PDFTo preview full article text in PDF format click here

Get Free ReaderYou could obtain free Acrobat Reader from Adobe


Copyright © International Olympiad in Informatics, 2017
Vilnius University, 2017