- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Roberto E. Vargas Caballero <k0ga_AT_shike2.com>

Date: Wed, 17 Sep 2014 00:16:22 +0200

*> 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,

Date: Wed, 17 Sep 2014 00:16:22 +0200

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 CaballeroReceived on Wed Sep 17 2014 - 00:16:22 CEST

*
This archive was generated by hypermail 2.3.0
: Wed Sep 17 2014 - 00:24:07 CEST
*