Thread: Algorithms

  1. #1

    Algorithms

    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.
    -Save the whales. Collect the whole set.

  2. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    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).

    http://www.google.com/search?q=summa...utf-8&oe=utf-8

    Whole bunch of stuff about the sigma.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  3. #3
    Sweet! I guess my memory's fading. What does the O(n) stuff mean? Any links for that? Thanks!
    -Save the whales. Collect the whole set.

  4. #4
    Registered User
    Join Date
    Apr 2002
    Posts
    362
    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.

    Code:
    for (double x = 1; x < 20000000000; x++)
         n += (pow(-1, n)) / (2 * n + 1);
    
    pi = 4 * (1 + n);
    (Okay, so I was bored! Sue me! )

    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.

    -Skipper
    "When the only tool you own is a hammer, every problem begins to resemble a nail." Abraham Maslow

  5. #5
    booyakasha
    Join Date
    Nov 2002
    Posts
    208
    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.

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >What does the O(n) stuff mean? Any links for that?
    http://www.google.com/search?hl=en&i...Big+O+notation

    -Prelude
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting algorithms, worst-case input
    By Leftos in forum C++ Programming
    Replies: 17
    Last Post: 06-15-2009, 01:33 PM
  2. page replacement algorithms?
    By Extrovert in forum C++ Programming
    Replies: 1
    Last Post: 08-19-2005, 12:53 AM
  3. relative strength of encryption algorithms (blowfish, des, rinjdael...)
    By duck-billed platypus in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 12-30-2001, 04:20 PM
  4. C Algorithms
    By Garfield in forum C Programming
    Replies: 2
    Last Post: 09-28-2001, 02:59 AM