PDA

View Full Version : Big Oh notation, help me notate this



Jeremy G
05-12-2005, 02:41 PM
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


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.

Sang-drax
05-12-2005, 03:27 PM
Both algorithms are O(n^2). The second one is always twice as fast, though.