Name: Anonymous 2015-05-04 23:22
How often is the answer to a tricky programming problem to use a fancy data structure?
What is a fancy data structure to you?e.g. those detailed in this course:
Classic case of Mortgage-driven Software Development: -23
Shifting or copying an array is still cheaper than traversing a list in most cases (see L1, L2, etc. cache), and even in the rare case that it's not, the tradeoff is O(n) for random access read and write.
Appending and popping is O(1) for both structuresYou need to take CS 101 course or whatever. Appending and popping for an array aren't O(1).
struct array {
int *objs;
int size;
int capacity;
};array.objs[array.size++] = value;array.size--;So append is actually O(n)Good thing you've finally noticed.
but still Θ(1)No, it's still Θ(n). You have to allocate a new, larger array, then copy all the n items from the old array to the new, then free the memory taken up the the old array.
No, it's still Θ(n). You have to allocate a new, larger array, then copy all the n items from the old array to the new, then free the memory taken up the the old array.
size and capacity vars. size is the number of elements in the array. capacity is the memory allocated to the array. size is always less than capacity. e.g. Initialize with size = 0 and capacity = 1024. That gives you 1024 O(1) append operations before capacity needs to be increased and objs needs to be reallocated. It's Θ(1), trust me. No, it's still Θ(n). You have to allocate a new, larger array, then copy all the n items from the old array to the new, then free the memory taken up the the old array.Someone did not read the post he is replying to.