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?

Wat do? back to the imageboards!

Read SICP.

>>2
Oh, so this place is for bitching and trolling aswell it seems.

>>1
Consider using a linked list instead of an array, or a data structure with reasonable prepending/appending time complexity.

>>1
It sounds like you are reinventing van Emde Boas trees. vEB uses an auxilary tree to hold usage information. You can also use this trick: http://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time/

>>4
A linked list will give me problems in insertion aswell since the access to the pointers won't be done in O(1).

>>5
Actually I'm implementing vEB, and that's why I'm so concerned with run times.

I'm checking what you just posted, I'll implement it right away and see how fast it turns out to be. Thank you!!

OP back to report.

FUCK YES!! It's working in a O(1) time! Thank you >>5!! I'm fucking bookmarking that page.

Fine, feel free to ignore the thread. I have what I needed. Thanks guys!

failing at algorithm analysis

...Waaait. Is calloc a O(1) function? Apparently it's not. Fuck, should I consider that time on my algorithm? I can control the NULL pointers stuff but calloc is going to be harder to override...

>>9
Time complexity doesn't work the way you think it does.

>>9
That is because calloc already initializes the memory to 0.

>>9
Newsflash: neither are malloc and free. Also see >>10.

>>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.

This question just doesn't make sense from a hardware pov, if you want to have values in memory you'd have to write to it.

If you use some pointer wizardry to work your way around it that's fine but don't call it something that it isn't.

>>11
Yep just realized that. Thanks.

>>10
>>12
>>13
I don't really mind if calloc is resource intensive and I do know it has to do with the time added when input is increased, and I know it might be actually taking little to no time to do the allocation. I'm using calloc in such a way it depends on the number of child nodes, so it's not constant time for sure. And since it's not a basic operation, but a function call, I can't disregard it from my analysis.

However I might be wrong, because the insert function needs to search in lg lg u nodes at most before appending, so yeah, maybe it's not as important as it seems.

>>14
I don't mind the hardware right now. Time is what matters.