Re: [dev] [RFC] Design of a vim like text editor

From: Roberto E. Vargas Caballero <>
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)


Roberto E. Vargas Caballero
Received 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