Big O notation for a copy operation

Question

I've come across some code which could definitely be improved, but i'm wondering about the Big-O notation of my improvements.

Their original code adds a element to an array, and each time it does this it creates a new array of n+1 and copies the old one in like so:

public MyType GetNewType()
{
    MyType[] tempTypes = new MyType[_types.Count + 1];
    _types.CopyTo(tempTypes, 0);
    _types = tempTypes;

   _types[types.Count - 1] = new MyType();
   return _types[types.Count - 1];
}

As far as I can see this would be a O(n) operation. I therefore rewrote it as follows:

private int _currentIndex; //initialized in the constructor

public MyType GetNewType()
{
    if (_types.Length == _currentIndex)
    {
        MyType[] tempTypes = new MyType[_types.Length + 10];
        _types.CopyTo(tempTypes, 0);
        _types = tempTypes;
    }

   _types[_currentIndex] = new MyType();
   _currentIndex++;

   return _types[_currentIndex - 1];
}

Would the result of these changes mean that the function will now run in O(n / 10) as it would only require a copy operation every 10 calls? Or does it not quite work as nicely as that?

Are you asking for the performance of the function, or the function and whoever is calling it? O(n / 10) == O(n), since 10 is a constant. — Stealth Rabbi, Oct 18 '11 at 16:24
The complexity for whoever is calling it I think? If it `GetNewType()` was called 10 times would that effect the big-o notation? — Joey Ciechanowicz, Oct 18 '11 at 16:35

score 3 · Answer 1 · answered Oct 18 '11 at 16:22

3

In terms of Big-O notation complexity of the (n/10) would be O(n) because it does not care such a small constants.

answered Oct 18 '11 at 16:22

sll

61,540
22
104
156

A factor of 10 is really not a small constant. – MGZero Oct 18 '11 at 16:26
@MGZero : in terms of Big-O even `10000` is a constant which does not matter because O-complexity cares of function growth on very very big number of elements (big `n`) – sll Oct 18 '11 at 16:29
@MGZero - but that's not really the point of Big O notation; as "sll" says it does not care about constants. – Reddog Oct 18 '11 at 16:36
I'm not familiar with sll, what is that? Also, for the record, I was not the one who downvoted. – MGZero Oct 18 '11 at 17:07

score 2 · Accepted Answer · answered Oct 18 '11 at 16:22

2

This is a common and good optimization. It's usually called "amortized constant time", which means most of the time, it's O(1) to add a single element, except when it's not. Often implementors will double the size of the array, or at least multiply by 1.5, instead of just adding ten elements.

That said, C# has some perfectly lovely built-in list classes which do this all for you, automagically, and using them is to be preferred over using bare arrays, whenever possible.

answered Oct 18 '11 at 16:22

Ernest Friedman-Hill

80,601
10
150
186

So 9/10th's of the time its O(1) and that's all we worry about? How about if the 1/10th's of the time was a hugely expensive operation, would that change it from O(1)? – Joey Ciechanowicz Oct 18 '11 at 16:31
4

Actually, I think you'll find that you *need* to multiplicatively increase the size of the array to get it to amortized O(1) time. When you e.g. double the array, starting with an array of size 1 and adding 2^n - 1 elements, you must perform n - 1 doublings (necessitating a copy of the entire array, depending on implementation)... the summation is such that to add 2^n - 1 elements takes about 2^(n+1) time which is O(2^n), and the per-add time is O(1) since O(2^n)/O(2^n) = 1. When you add 10 each time, the summation ends up O(n^2), so the amortized per-add time is actually O(n), I think. – Patrick87 Oct 18 '11 at 16:43
Note that growing array by 10 entries will give you amortized O(n), but growing size by percentage (i.e. twice) gives O(1). Check out http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist for discussion (Java, but C# is the same for this). – Alexei Levenkov Oct 18 '11 at 16:45

score 2 · Answer 3 · answered Oct 18 '11 at 16:36

Amortized constant time works only if you DOUBLE the size of the array each time you run out of free items! If not, averaged big O notation will be always O(n).

C# List implementation doubles the size of the array each time the list count is equal to capacity.

To make your insertion method averaged O(1) you need to so something like this:

MyType[] tempTypes = new MyType[Math.Max(8, _types.Length * 2)];

Big O notation for a copy operation

3 Answers3