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
for all agents (n)
for all agents (n) > current
check this agent against that

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.

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