>>49
Yes, malloc is expensive >>53
Generally you'd want a linked list of static arrays to implement a dynamic array so (when triggering a resize) you don't have to realloc and hope for another contiguous chunk of memory that is bigger than the current one you have.
Lookup is O(n/pagesize).