1

Possible Duplicate:
are there any O(1/n) algorithms?

Is it ever possible for your code to be Big O less than O(1)?

Community
  • 1
  • 1
dreadwail
  • 15,098
  • 21
  • 65
  • 96

3 Answers3

9

O(1) simply means a constant time operation. That time could be 1 nanosecond or 1 million years, the notation is not a measure of absolute time. Unless of course you are working on the OS for a time machine, than perhaps your DoTimeTravel( ) function would have O(-1) complexity :-)

Ed S.
  • 122,712
  • 22
  • 185
  • 265
2

Not really. O(1) is constant time. Whether you express that as O(1) or O(2) or O(.5) really makes little difference as far as purely big O notation goes.

As noted in this question, it is technically possible to have an O(1/n), but that no real-world useful algorithm would satisfy this (though some do algorithm's do have 1/n as part of their algorithmic complexity).

Community
  • 1
  • 1
Matthew Scharley
  • 127,823
  • 52
  • 194
  • 222
  • The sql statements like "DROP TABLE" and "DELETE FROM TABLE" Show O(1/N) beheaviour. – James Anderson Aug 17 '09 at 06:21
  • How do you figure that? `n` being the number of tables, not the number of records in the table, since the *table* is the input, and usually all these operations need to do is delete a reference to the table. – Matthew Scharley Aug 17 '09 at 06:26
  • `DELETE FROM TABLE` might have O(1/N) characteristics, dependant on implementation, but I would doubt if this would show up unless you were trying to delete over half the table. – Matthew Scharley Aug 17 '09 at 06:31
0

The only thing that would take less than O(1) (constant time) would be an operation that did absolutely nothing, and thus took zero time. But even a NOP usually takes a fixed number of cycles...

Peter
  • 127,331
  • 53
  • 180
  • 211