GSoC/GCI Archive
Google Code-in 2011 GNOME Project

Investigate the algorithmic complexity of GLib data structures

completed by: Alex Palcuie

mentors: David King

  • Investigate the algorithmic complexity, and document it using big O notation, for each function in the data structures GSList, GList, GHashTable and GTree. Example: g_list_find() or g_list_remove() are O(n) where n is the length of the list. Mention common pitfalls for functions which are normally called in repeated fashion, such as g_list_append() (it is O(n), but calling it to build a list results in O(n^2) behavior)
  • Expected results: A new bug report against the GLib product, with the big O notation of each data structure function in a comment.
  • Requirements: C programming knowledge, basic knowledge of algorithms, English