> No. Because the realloc that you have to do maybe has to move in the
> worst case n-1 elements in a new memory arena. So you have n (moving
> to the position) * n-1 (memcpy to new position in memory) = n^2. You
> can decrease the possibility of reallocation allocating
> more memory of needed, but when you have the reallocation you get
> the O(n^2). In a list you don't have ever a reallocation.
Upps, I mistook here. It is 2n, that means a complexity of O(n), so
in this point you were right, but it doesn't change too much the discusison.
For a resume of these complexity see this table I took in some place:
Linked list Array Dynamic array Balanced tree
Indexing O(n) O(1) O(1) O(log n)
Insert/delete at beginning O(1) N/A O(n) O(log n)
Insert/delete at end O(1) N/A O(1) amortized O(log n)
Insert/delete in middle search time
+ O(1) N/A O(n) O(log n)
Wasted space (average) O(n) 0 O(n)[2] O(n)
Regards,
--
Roberto E. Vargas Caballero
Received on Wed Sep 17 2014 - 00:16:22 CEST