Today, I was trying to motivate the study of time series (FFT in particular) and methods of discrete and continuous Mathematics in particular by a short exposition of <i>generating functions</i>. Here's another motivational example: optimization (continuous) and summation (discrete) leading to the solution of a problem from homework assignment 2:
<P>
Assume an implementation of Priority Queue (PQ) that allows logarithmic meld of two queues. Consider one <b>round</b> of the "round robin" algorithm, in which all the <i>2k</i> original PQs are melded into <i>k</i> queues with the total of <i>n</i> elements. If the <i>i</i>th resulting PQ holds <i>n_i</i> elements, the round takes &#931;(log n_i) = log(&#928;(n_i)), where &#931;(n_i)=n. Under this constraint, the product attains maximum when the factors are equal and thus log(&#928;n_i)&#8804;log((n/k)^k)&#8804;k*log(n/k). If we now sum this upper bound on the time complexity of each round, we obtain (with some effort) the bound of n*&#931;(i/2^i) &#8804; n, the desired linearity of the round robin (multi-phase) melding.