Thread: Big Oh notation, help me notate this

  1. #1
    mov.w #$1337,D0 Jeremy G's Avatar
    Join Date
    Nov 2001
    Posts
    704

    Big Oh notation, help me notate this

    I kinda forgot to pay attention when this was gone over in class, but I picked up the general gist of it.

    Basically O() aproximates worst case scenarios AFAICT.

    Now, as seen on my website (jeremygiberson.com) i have a flash AI demonstration. I'm trying to come up with the O() notation for it.


    In my script I have this (psuedo code) for position updates
    Code:
    for all agents (n)
         for all agents (n)
              check this agent against other agent
    Now I THINK the notation for this is O(n^2).

    But I think this also represents the permutation for N objects, pick 2 (order matters)

    Now, and optimazation I'm thinking of modifying the code to be combinative (is that a word?) such that the new psuedo code is
    [code]
    for all agents (n)
    for all agents (n) > current
    check this agent against that
    [code]

    If I'm not off my hump, this should resemble nC2.


    The question is this: Is my first O(n^2) guess correct, and second is the guess O(n*n!) correct / close to what would be represented by the second psuedo code?


    Please feel free to correct me on any mis-interpritations of the algorythem.

    EDIT: I alwasy reverse Permutations, and Combinations. As such this post was altered to reflect correction.
    Last edited by Jeremy G; 05-12-2005 at 02:52 PM.
    c++->visualc++->directx->opengl->c++;
    (it should be realized my posts are all in a light hearted manner. And should not be taken offense to.)

  2. #2
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Both algorithms are O(n^2). The second one is always twice as fast, though.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. big O notation question
    By l2u in forum C++ Programming
    Replies: 7
    Last Post: 11-08-2008, 03:53 PM
  2. Big Oh Notation problem
    By vaibhav in forum C++ Programming
    Replies: 4
    Last Post: 04-01-2006, 09:02 AM
  3. about big O notation
    By deepakkrmehta in forum C Programming
    Replies: 3
    Last Post: 08-27-2005, 02:31 PM
  4. big o notation
    By heat511 in forum C++ Programming
    Replies: 5
    Last Post: 04-19-2002, 11:27 AM
  5. Big O Notation
    By Drew in forum C++ Programming
    Replies: 1
    Last Post: 09-30-2001, 01:22 AM