didactic analysis of merge sort

Dátum
2013-12-01
Folyóirat címe
Folyóirat ISSN
Kötet címe (évfolyam száma)
Kiadó
Absztrakt

Due to technical difficulties, educators teaching merge sort often avoid the analysis of the cost in the general and average cases. Using basic discrete mathematics, elementary real analysis and mathematical induction, we propose a self-contained derivation of bounds αn log_2 n + βn + γ in all cases. Independent of any programming language or pseudo-code, supported by intuitive figures, it is suitable for informatics students interested in the analysis of algorithms. It is also a good exercise in showing that induction allows us to actually discover constants, instead of simply checking them a posteriori.

Leírás
Kulcsszavak
didactics of informatics, analysis of algorithms, cost analysis, merging, merge sort, enumerative combinatorics
Forrás
Teaching Mathematics and Computer Science, Vol. 11 No. 2 (2013) , 195-210