Hashing

Data Structure Hashing | Hashing in Data Structure | Data ...

Re: O(1) and similar measures of complexity (sometimes called "Big Oh Notation").

The intention is to give some measure of how complex the code needed to implement the algorithm is (or, practically speaking, how fast the code can execute) for different algorithms / strategies, in relation to the amount of data that must be dealt with.

You will typically see other instances denoted like some of these: O(1), O(n), O(log n), O(n^2) (i.e., n squared).

The idea is that the typical processing time needed to (for example) select a desired piece of data given a larger quantity of data to select from is:

• O(n^2) (i.e., n squared): proportional to the amount of data squared
  
• O(n): proportional to the amount of data
• O(log n): proportional to the log(arithm) of the amount of data
• O(1): constant--it takes a certain amount of time to process one piece of data no matter how much data you have to select from

Note that the proportionality constant is not specified in the big O notation, so for small quantities of data you might find that an algorithm which is very simple but is O(n^2) may actually be better than one at O(1), but as your dataset gets bigger, things with a lower big O "value" are better.

As an example, programming a hash takes a fair amount of programming effort, but gives O(1).

Not all problems can be solved with an algorithm at O(1).

Kinda like a dB?

Well, there is some relation there, I mean, dBs work on a logarithmic scale. ;-)

Big O's can indicate proportionality to a constant, to log n, to n, to n^2, to n^3, ..., even to things like n^n or worse, for complicated problems.

dBs are all based on logarithms (only), and usually an actual number is specified. In big O notation, you usually don't specify a number or proportionality constant--algorithms could be rated so precisely as to be proportional to n, or 1.5 n, or 2 n, ..., but usually it is enough to know that a given algorithm is proportional to n (or log n, or n^2, or whatever).

Also, the exact proportionality constant depends on things like the skill of the programmer and how well a given programming language is for expressing a particular kind of problem.

Sometimes it is important to know the proporitionality constant, but then you may actually have to program two competing algorithms in your target language, and then compare the actual results. I sort of alluded to that in my first post.

For (a bad) example, consider an O(n) algorithm with a proportionality constant of 27, and compare that to an O(n^2) algorithm with proportionality constant 1. For data sets of size 26 or smaller, the O(n^2) algorithm is actually better (i.e., faster) and probably tends to a brute force / simple minded approach that is easier to program.

PS: I don't think the term "proportionality constant" is typically used in "the literature"--I just couldn't think of a better term off the top of my head.

This is all soooooooooo far over my head that I'm getting a nose bleed.

lol--sorry! It's really not that complicated--I probably haven't thought of a good approach or example for explaining it.

I'm sure you've done some programming, and recognize that some approaches to a problem are simpler than others. Sometimes (often?) the approaches that are simple to program aren't very clever, and take a long time to execute.

Another more clever approach may be faster to execute, but may require a lot of effort to program. (Or a lot of execution overhead--a hash requires that there be a hash table, set up by the program in advance (while the program is running, but before the hash can be used).) (And, the hash table also trades off execution speed for memory space.)

Anyway, try some ice ;-)

Thanks, that's better.