what does O(N) mean

Question

Possible Duplicate:
What is Big O notation? Do you use it?

Hi all,

fairly basic scalability notation question.

I recently recieved a comment on a post that my python ordered-list implimentation "but beware that your 'ordered set' implementation is O(N) for insertions"

Which is great to know, but I'm not sure what this means.

I've seen notation such as n(o) o(N), N(o-1) or N(o*o)

what does the above notation refer to?

Answer 1

The comment was referring to the Big-O Notation.

Briefly:

1. O(1) means in constant time - independent of the number of items.
2. O(N) means in proportion to the number of items.
3. O(log N) means a time proportional to log(N)

Basically any 'O' notation means an operation will take time up to a maximum of k*f(N)
where:

k is a constant multiplier

f() is a function that depends on N