What is the space requirement of many trees?

Question

I was asked the space requirements of my project and I wasn't sure about the answer, so I am asking here. Here is what I do:

1. I am building a number of perfect binary trees (let's say m).
2. Every leaf indexes one point (i.e. that we keep the data stored and every tree indexes the points that are stored there).

My thought is that the space requirement is: O(n*d + m), where n is the number of points, d is the dimension of a point and m is the number of the trees, but I am telling this by experience, not sure if I fully understand it!

Can anyone help?

---

To be honest, every leaf contains a number of points, p, but I think that I will be able to work out the result, if I will get an answer to my question above.

Answer 1

In a perfect binary tree with n leaves, the total number of nodes is 2n - 1, which is O(n). More generally, if you have a collection of perfect binary trees with n total leaves, the total number of nodes will be 2n - 1. Therefore, if each of the n leaf nodes stores a d-dimensional point, the total space usage is O(nd).

The number of trees m here actually doesn't need to show up in the big-O space analysis. Think of it this way: if you have m trees, assuming each is nonempty, then you have to have at least n leaf nodes (at least one per tree), so we know that m = O(n). Therefore, even if you do account for the space overhead per tree as O(m), the total space usage of O(nd + m) is equivalent to O(nd).

Hope this helps!