none
Is Collection<T>.RemoveAt really an O(n) operation? RRS feed

  • Question

  • Documentation for List<T>.RemoveAt
    http://msdn.microsoft.com/en-us/library/5cw9x18z.aspx
    says that removing an item is an O(n) operation where n=Count-Index. 

    Documentation for Collection<T>.RemoveAt
    http://msdn.microsoft.com/en-us/library/ms132414.aspx
    says that removing an item is an O(n) operation where n=Count.

    Question 1: Why is removing from a collection by index less efficient than removing from a list?

    Documentation for Collection<T>.Remove
    http://msdn.microsoft.com/en-us/library/ms132413.aspx
    also says that removing an item is an O(n) operation where n=Count.

    However, the Remove method calls the RemoveItem method.  Presumably what happens is this:

    1) Remove method establishes the index of the item, using IndexOf
    2) Then, calls RemoveItem, passing in that index.

    Both of these steps are documented as O(n) operations.

    Question 2: Doesn't this imply that Collection<T>.Remove is really an O(2 * n) operation where n = Count?

    Question 3: Why isn't removing an item by its index in a collection just an o(1) operation?  Is it because of the renumbering of all subsequent items?

    Cheers!
    Sunday, February 8, 2009 3:07 PM

Answers

  • The docs are incorrect.  Easily verified:

    using System;
    using System.Collections.Generic;
    using System.Collections.ObjectModel;
    using System.Diagnostics;

    namespace ConsoleApplication1 {
      class Program {
        static void Main(string[] args) {
          var coll = new Collection<int>();
          for (int ix = 0; ix < 100000; ++ix) coll.Add(ix);
          var sw = Stopwatch.StartNew();
          while (coll.Count > 0) coll.RemoveAt(0);
          sw.Stop();
          Console.WriteLine(sw.ElapsedMilliseconds);
          for (int ix = 0; ix < 100000; ++ix) coll.Add(ix);
          sw = Stopwatch.StartNew();
          while (coll.Count > 0) coll.RemoveAt(coll.Count - 1);
          Console.WriteLine(sw.ElapsedMilliseconds);
          Console.ReadLine();
        }
      }
    }

    Output:
    4494
    3

    Q2: that's not how big-Oh notation works.  It is just a bigger Oh.

    Q3: List<> (Collection<>'s underlying collection object) is implemented as an array to make indexing O(1).  If you want O(1) perf for removing items, you'll have to use LinkedList<>.


    Hans Passant.
    • Marked as answer by Zhi-Xin Ye Friday, February 13, 2009 8:18 AM
    Sunday, February 8, 2009 3:36 PM
    Moderator