Hot answers tagged

2

The number of octrees with $n$ nodes is OEIS sequence A007556: $$T(n) = {8n \choose n}/(7n+1)$$ I worked this out, incidentally, by writing a short program to generate the first few values of $T(n)$ and then searching for it. If you had no other information than $n$, then the minimum number of bits required to store an octree with $n$ nodes is $\log\,T(n)$...


1

Since the data structure is only created once, you can simply use an array ordered by the key. Each element in the array contains the key-value pair. Sorting the array is O(n*log(n)), which will be fast for 4e6 items and only needs to be done once. You can then use binary search (which is O(log2(n) or ~22) on the array to find the key. If not found, ...


Only top voted, non community-wiki answers of a minimum length are eligible