128 reputation
2
bio website morrellplumbing.com.au
location
age
visits member for 1 year, 7 months
seen Jan 28 '13 at 22:30

Full time business manager part time programmer for in-house applications only - don't expect any polish!


Jan
22
awarded  Scholar
Jan
22
accepted Algorithmic order of table indexes for table operations
Jan
22
comment Algorithmic order of table indexes for table operations
Thanks for a comprehensive answer, however, it is not the answer to the question I posed. My question related to algorithms which are mathematical constructs that run on Turing machines; your answer is about programs that run on real computers. The order of an algorithm simply relates to the number of steps; the speed of a program depends critically on how long those steps take as well. I think, from your answer, that I have it essentially correct, yes? The insight about hash tables is one I hadn't considered. Thank you. Perhaps this should be on Mathematica?
Jan
21
awarded  Student
Jan
18
comment Algorithmic order of table indexes for table operations
let us continue this discussion in chat
Jan
18
comment Algorithmic order of table indexes for table operations
I understand and agree with what you have said but on a 100,000 row table O(n)~100,000 and O(n)~6. You would need about 10,000 indexes to even get close!
Jan
18
comment Algorithmic order of table indexes for table operations
But updating each index is only an O(log(n)) operation, for any decent value of n you have saved by making the initial lookup O(log(n)) instead of O(n). For indexes*log(n)>n you are going to need significantly more indexes than records!
Jan
18
comment Algorithmic order of table indexes for table operations
I don't think that is correct - the overhead caused by the updating of the index is less than the saving that you get in the initial lookup.
Jan
18
asked Algorithmic order of table indexes for table operations