diff options
author | Emmanuel Fleury <emmanuel.fleury@gmail.com> | 2019-08-06 20:59:46 +0200 |
---|---|---|
committer | Emmanuel Fleury <emmanuel.fleury@gmail.com> | 2020-09-02 14:38:15 +0200 |
commit | 54c20c8532e9faf643fb4b06f65590fa15236970 (patch) | |
tree | bc7c5601f042e60afadd0984d0f308a99a2b6a7d /glib/gsequence.c | |
parent | a62fcb9af11eee964731645bc3f68ebf8f37344b (diff) | |
download | glib-54c20c8532e9faf643fb4b06f65590fa15236970.tar.gz |
Add some notes on complexity in glib/gsequence.c
Related to issue #3
Diffstat (limited to 'glib/gsequence.c')
-rw-r--r-- | glib/gsequence.c | 5 |
1 files changed, 4 insertions, 1 deletions
diff --git a/glib/gsequence.c b/glib/gsequence.c index c0fa9d6c9..96f21d6e4 100644 --- a/glib/gsequence.c +++ b/glib/gsequence.c @@ -30,7 +30,10 @@ * * The #GSequence data structure has the API of a list, but is * implemented internally with a balanced binary tree. This means that - * it is possible to maintain a sorted list of n elements in time O(n log n). + * most of the operations (access, search, insertion, deletion, ...) on + * #GSequence are O(log(n)) in average and O(n) in worst case for time + * complexity. But, note that maintaining a balanced sorted list of n + * elements is done in time O(n log(n)). * The data contained in each element can be either integer values, by using * of the [Type Conversion Macros][glib-Type-Conversion-Macros], or simply * pointers to any type of data. |