Posted by T.Gracken on September 12, 2002 at 21:34:08:
In Reply to: ah, recursion ... posted by Joel on September 12, 2002 at 17:48:47:
: I were playing around with a recursive "quicksort" function a few months ago, & what a perplexing, yet fascinating, beast that was! I expect that recursion will be rearing its ugly head again this semester, in Data Structures.
definitely...
: Yes, now that you point it out, of course what I meant was f(n) = sum[from j=1 to n] g(j) where g(j) = j (or, in another instance, g(j) could be defined as some other function of j). Thanks for straightening me out.
: But what I still haven't managed to elicit from you is the NAME for this TYPE of function (if it has one).
: This is a quadratic function: f(n) = an^2 + bn + c
: This is a ?????????????: f(n) = sum[from j=1 to n] j
as far as a name... we are in a different realm. a quadratic is a polynomial of degree 2. there are higher order polynomial functions, rational functions, logarithmic functions, exponential functions, et.al. (and I know you have encountered all of these so far...)
what you are considering when looking at a "sum" is generally referred to as a "series".
of course, (just to mess with you), there are different types of series. But I will restrict this to what are called finite and infinite series.
that puts us in the catagorie of a list with a fixed number of elements or an infinite list.
example: add the natural numbers from 1 to 1000. this is a finite series where we are adding a fixed number of values. easily evaluated due to your own observations (or other dead peoples observations) of sequences. This is generally referred to as an arithmetic series.
example: add all numbers in the sequence .3, .03, .003, .0003, .00003, etc.
even though this is a sequence that contains an infinite number of terms, there is a specific result if one considers adding every term in the list (which continues FOREVER). it is 1/3. this is referred to as the sum of an infinte (geometric) series.
so although there may be a "name" for a function defined by a sum (as you have set up), I am not sure that there is a generaic term or name for such a sum (other than a series).
however, in the words of many others... I could be wrong... I am just wearing a monkey suit.