4 ms·
What is the computational complexity of looking up, adding and deleting a single row? Is it comparable with binary trees [O(n log n)] and hashtables [O(1) on a
by niutech 11y ago
What is the computational complexity of looking up, adding and deleting a single row?
Is it comparable with binary trees [O(n log n)] and hashtables [O(1) on average]?
- geedy 11y agoThat is one area LittleD needs some improvement. We only support CREATE TABLE, INSERT, SELECT right now. O(1) for inserts because we only append. That said, IonDB was in part motivated to be a storage engine for LittleD. Then you basically get exactly what you described: your choice of underlying dictionary data-structure for the performance characteristics you need. It will also make UPDATE/DELETE a breeze, once we incorporate the two code-bases!
- schrodinger 11y agoBinary trees are log(n), not n*log(n)
- niutech 11y agoYou're right. n*log(n) is for building the BST in Tree sort.