I thought this board would be the best place to post this, mods feel free to move it, but I'll be using it for C++ so whatever...
Anyway, I was looking at a book containing lots of algorithm info at my local college and I was wondering what the thing that measures the speed means. In this book it was represted by a sigma with n on the top or something? Does anyone know what I'm talking about? Any help, or a link to website about it would be much appreciated.
sigma with an n over top? It's probably a summation from the thing on bottom of the sigma to n of the stuff to the right. I'd assume that was somewhere in the middle of the derivation of the running time however. Likely it ends with an O(some function of n).
Whole bunch of stuff about the sigma.
Sweet! I guess my memory's fading. What does the O(n) stuff mean? Any links for that? Thanks!
Speed (velocity) and acceleration are functions of calculus (speaking from the standpoint of 'physics').
What you are describing (the 'sigma' thing) is the summation of a function over a range of values, typically 0 to n, or n-1.
As an example, a method for calculating pi is to use the formula:
4 * (1 + ((pow(-1, n)) / (2 * n + 1))) where n begins at '1', (a departure from a FOR loop beginning at '0'), and ends...wherever we choose.
(Okay, so I was bored! Sue me! :rolleyes: )
for (double x = 1; x < 20000000000; x++)
n += (pow(-1, n)) / (2 * n + 1);
pi = 4 * (1 + n);
Yes, I ran 20 G iterations to come up with pi accurate to, maybe, ten decimal places. Almost four hours on my machine, truth be told. Should try it on the kids' machine which I recently upgraded to a 2.53 GHz processor, but...
...I digress. The FOR loop above is an example of a summation over a range of values for a given function. As with calculus, the more values contained within that range, the greater the accuracy of the result.
O(n) or O(n^2) or whatever is called Big-O notation ; It gives theoretical speed ( or maximum growth )
for example f(n) = O(n^2) basically means that for large values of n function f(n) grows slower then n^2 and will basically run at the same speed.
so O(n) is better then O(n^2)
O(n) is worse then O(1/n)
and O(n^n) is worse then all these
You should look up Big-O Notation
and also look up Omega, Theta and little-O Notation
They are each a little different.
>What does the O(n) stuff mean? Any links for that?