A Warm-up
Paolo Ferragina · Cambridge University Press eBooks · 2023
This chapter deals with a classic educational problem, called the subarray sum. The specialty of this problem is that it has a simple formulation, which finds other useful variations and applications, and it admits a sequence of algorithmic solutions of increasing sophistication and elegance, which imply a significant reduction in their time and I/O complexities. Te ultimate result is a linear-time and -I/O algorithm, which will allow the reader to enter into the “game” of time and I/O complexity evaluations. The chapter concludes with a discussion of some interesting variations of this problem which arise from computational biology applications, and admit no immediate algorithmic solutions, thus stressing the fact that “ five minutes thinking” is not enough for designing efficient algorithms.