Filling a pointer array with NULL in O(1)

Well, this is my first time posting in the text board, so...

I asked in /g/ already and I have some questions. My problem is as follows.

I'm building a tree structure in C. Each level has an array of pointers that point to the following node. The amount of pointers depends on the level too, so a lower level node will have less pointers than the father. An insertion in this structure has a O(lg lg n) complexity. However, building the node is using O(u) for u child nodes. And at times I need to build the node in the middle of the insertion function. This is slowing significantly the run time and adding a complexity time the function shouldn't have.

I was thinking of using a char variable initially set to zero, and if the amount of pointers to be allocated exceeds 8 I can resize the char variable with realloc. A zero in the i-th bit means the i-th node is not pointing to a node. I don't know how much time will this take and I don't know if it'll be too costly to search for a specific byte.

Then there's this function, memset. It seems awesome and all but I don't know how much time it takes.

I need this node building function to take O(1) or a really reasonable time so it doesn't make the whole function slower than it should be.

Wat do?

>>9 See >>10

Time complexity has little to do with how much literal time things take, more, the proportionate time added when input is increased. Stop using Big-Oh notation to describe how long a function takes, it doesn't make sense. You really should be asking if calloc is resource intensive.