On examining the red black tree used for the SortedDictionary class, I realized Microsoft did not use any recursion for insertion and deletion. This seems weird, because I have never come across a top-down tree balancing method. Then I found the Eternally Confuzzled - Red Black Tree Tutorial, which clearly explains how it is done. Thanks Julienne!

## Monday, March 29, 2010

## Sunday, March 28, 2010

### Runtime Complexity of .NET Generic Collection

I had to implement some data structures for my computational geometry class. Deciding whether to implement the data structures myself or using the build-in classes turned out to be a hard decision, as the runtime complexity information is located at the method itself, if present at all. So I went ahead to consolidate all the information in one table, then looked at the source code in Reflector and verified them. Below is my result.

Note:

Update 25 April 2010: Added SortedSet

Internal Implement- ation | Add/insert | Add beyond capacity | Queue/Push | Dequeue/ Pop/Peek | Remove/ RemoveAt | Item[index]/ElementAt(index) | GetEnumerator | Contains(value)/IndexOf/ContainsValue/Find | |

List | Array | O(1) to add, O(n) to insert | O(n) | - | - | O(n) | O(1) | O(1) | O(n) |

LinkedList | Doubly linked list | O(1), before/after given node | O(1) | O(1) | O(1) | O(1), before/after given node | O(n) | O(1) | O(n) |

Stack | Array | O(1) | O(n) | O(1) | O(1) | - | - | O(1) | O(n) |

Queue | Array | O(1) | O(n) | O(1) | O(1) | - | - | O(1) | O(n) |

Dictionary | Hashtable with links to another array index for collision | O(1), O(n) if collision | O(n) | - | - | O(1), O(n) if collision | O(1), O(n) if collision | O(1) | O(n) |

HashSet | Hashtable with links to another array index for collision | O(1), O(n) if collision | O(n) | - | - | O(1), O(n) if collision | O(1), O(n) if collision | O(1) | - |

SortedDictionary | Red-black tree | O(log n) | O(log n) | - | - | O(log n) | O(log n) | O(log n) | O(n) |

SortedList | Array | O(n), O(log n) if added to end of list | O(n) | - | - | O(n) | O(log n) | O(1) | O(n) |

SortedSet | Red-black tree | O(log n) | O(log n) | - | - | O(log n) | O(log n) | O(log n) | - |

Dictionary | Add, remove and item[i] has expected O(1) running time |

HashSet | Add, remove and item[i] has expected O(1) running time |

Subscribe to:
Posts (Atom)