> Does anyone know what the running time of DmGetRecord() is? It appears from
> the docs it is O(1) but I am not sure. I am developing an application that
> could potentially have lots of records, so I want to make sure i'm not
> using any functions that have O(n) or similar running time.
In theory, it's O(n). In practice, it's O(1).
Rough story:
Record handles are stored in an array, so access given the record number is
just an array reference, which is constant time O(1).
Actual story:
But, note, that when you have lots of records (>8000), this array overflow
64K, so another list of records is created (list contains array of 8 bytes:
3 byte unique ID, 1 byte attr, 4 byte local ID). Actually, the overflow may
occur sooner: when a list can't be resized bigger, a new list is allocated.
So, if you've got 64K records in your database, you've got at least 8 lists,
which means doing a DmGetRecord on the last record causes 7 linked list
traversals.
Theoretically: accessing a record is:
O(n/k) = O(n). In practice, as long as you've got fewer than 8000
records, it's O(1).
Neil
--
Neil Rhodes
Calliope Enterprises, Inc.
1328 Clock Avenue
Redlands, CA 92374
(909) 793-5995 [EMAIL PROTECTED] fax: (909) 793-2545
--
For information on using the Palm Developer Forums, or to unsubscribe, please see
http://www.palmos.com/dev/tech/support/forums/
