[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Sv: A little more exact specification of the hash-table

Christian Reiniger wrote:

>>I hadn't thought of that. It's not exactly O(1), though, but rather O(c)
>>where c is a constant. Ie, constant-time performance.
>i.e. O(1) ;)
>The O notation always means "in the order of ...", i.e. 
>O(1) is constant (any constant, no matter how big),
>O(n) is linear (i.e. 1*n or 1000000000*n, doesn't matter)

Correction: the above is a bad explanation ;)
The O notation describes how something (usually processing time) roughly
behaves depending on a value n (usually input size). Thus,
O(1) means processing time is independent from the input size, constant
O(n) means processing time increases linearly with the input size
O(n^2) means ... increases quadratically with the input size

etc. That's the *only* thing the O notation expresses.


Drive A: not responding...Formatting C: instead