Re: O(n) analysis of Bubble and Selection Sort


"Alf P. Steinbach" <alfps@xxxxxxxx> wrote in message
news:ha28u1$42h$1@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
* arnuld:

I don't know how you type the letter SIGMA but I think SIGMA(i=0...
(size-1)) = size(size - 1)/2

Yes, if you mean the sum of the numbers 0 through size-1.

But your notation is a bit off.

SIGMA is not an ordinary function. It's the greek uppercase letter
corresponding to Latin "S", short for "Sum". You can regard it as a
function

S(values, f) -> sum

producing the sum f(x1) + f(x2) + f(x3) + ... + f(xn) where xN are the
values in the set 'values'.

But instead of writing e.g.

f(x) = x^2
S( {1...n}, f ) = 1^2 + 2^2 + 3^2 + ... + n^2 = something

we write

n
SIGMA i^2 = 1^2 + 2^2 + 3^2 + ... + n^2 = something
i=1

It's just a more compact way to express the first, avoiding the need to
name the function f (or use lambda notation).

The problem with your expressions is that you have left out the
specification of f.


I personally often use the notation:
sum(n, i=1) i^2

and several of my past scripting languages use a notation sort of like this.


hmm, if added as a C compiler extension:
x = __sum(n; i=1) pow(i, 2);

but, then again, if one were to do this, then it would be almost expected
that one would add in support for integrators, limits, derivatives, ...

but, then again, these are probably better done with library functions (and
function pointers).
similarly, built-in integrators and limits would likely be problematic.

but, then again, if one used a function pointer for these things (noting C's
lack of closures), then one is back to the issue that it would likely be
faster and more convinient just to do it manually via a loop...



.

Relevant Pages

  • Re: Polysigned A^A
    ... Using Golden's notation: ... and let RCbe the real group algebra ... of RCwhich is sum of the elements in C. ... I have no idea what "field contingencies" are. ...
    (sci.math)
  • Re: Polysigned A^A
    ... pair of zero divisors in P4. ... Using Golden's notation: ... and let RCbe the real group algebra ... of RCwhich is sum of the elements in C. ...
    (sci.math)
  • Re: 3-way numbers and arithmetic
    ... To sum these numbers, you sum the c parts together and keep the ... The OP's name "Bonsignore" appears to be ... considering European notation. ... with multiples of a* appearing in the first part. ...
    (sci.math)
  • Re: Advice for math phD programs: give up abstact algebra
    ... NOTATION, which are used to denote exactly the same element of Ras ... mathematics that is regarded as pristine. ... variable defined as real is not compatible in product or in sum with a ...
    (sci.math)