Possible Duplicate:
are there any O(1/n) algorithms?
Is it ever possible for your code to be Big O less than O(1)?
views:
325answers:
3
+2
A:
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).
Matthew Scharley
2009-08-17 06:09:05
The sql statements like "DROP TABLE" and "DELETE FROM TABLE"Show O(1/N) beheaviour.
James Anderson
2009-08-17 06:21:51
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
2009-08-17 06:26:29
`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
2009-08-17 06:31:50
A:
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
2009-08-17 06:11:28
A fixed number of cycles? How many cycles does it take to read an instruction and do nothing? I wouldn't expect a NOP to take more than 1 cycle...
Matthew Scharley
2009-08-17 06:13:06
Not really. It's constant, but it always takes time, atleast one cycle, but however long it takes to read the instruction and discard it.
Matthew Scharley
2009-08-17 06:29:40
+4
A:
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 Swangren
2009-08-17 06:13:22