Time complexity; C#

Replies to This Discussion

Permalink Reply by David Rutten on June 13, 2017 at 5:09am

You need to forget about details of your code and one-off things like declarations (more on those later btw.). Big-O runtime is about how much longer your algorithm will take if you increase the amount of data it has to operate on. So only those aspects of the algorithm that differ in these cases are relevant.

For example if your algorithm always does exactly the same thing (let's say all it does is measure the size of an array and display it on screen) will be O(1), because it doesn't matter if you run it on an array containing 10 or 1000000 items. Measuring the size of an array is a constant-time operation:

Print(string.Format("Array contains: {0} element(s)", data.Length);

However if your algorithm works on not on arrays but on linked-lists, then it becomes an O(N) operation because counting all the elements in a linked list means you have to iterate over all of them. And the longer the list, the more iterations you need. In fact the number of iterations is exactly the same as the number of items. (ps. if you'd be using the System.Collections.Generic.LinkedList<T> class then it's still O(1), because apparently that particular implementation of linked lists caches the count and keeps it up to date.)

If you have a loop that runs for each item, and then inside that loop there is another loop that also runs for each item, then your complexity becomes O(N²). Or, in a similar case if your algorithm consumes two collections (N and M) and iterates over all items in N, and then inside that loop it iterates over all items in M, the complexity is O(N×M).

The case can be made that only the most severe complexity is relevant enough to report. For example if you have an algorithm that comprises of three steps, the first of which is O(log(N)), the second is O(N²) and the third is O(3ⁿ), then technically the total complexity would be O(log(N) + N² + 3ⁿ), however the first two parts are utterly insignificant compared to the third and therefore can be omitted entirely. Consider for example increasing the input size from 10 to 20 elements:

• log(10) + 10² + 3¹⁰ = 1 + 100 + 59049 = 59150
• log(20) + 20² + 3²⁰ ≈ 1 + 400 + 3486784401 ≈ 3486784802

As you can see the increase of the complexity is almost entirely due to the O(3ⁿ) portion, so much so that there's almost no point in mentioning the other two.

Now, your specific questions:

1. Constructors/declarations and method invokes are not necessarily O(1). In this particular case they are, but it is possible that some constructor you call may have a higher complexity. For example if instead of an empty List<T> you're constructing a SortedList<T> based on your inputs, then it definitely may be the most significant complexity in your entire algorithm and it needs to be taken into account.
2. Correct. A loop like this has complexity O(N), ignore stuff that only happens once like the declaration of the iteration variable.
3. I don't understand that line of code. cP is already a list. Why are you calling ToList() on it? In general making copies of memory-contiguous collections (like arrays or lists) can be done in O(1), depending on implementation, because blocks of memory can simply be duplicated or moved at one go using the correct hardware ops. However other times it will require a loop in which the complexity goes up.
4. It's very cheap to add items to lists, provided the list has enough space to add new items. By default a list is big enough to contain only 4 items. If you try and add a fifth one, the list will need to allocate more memory elsewhere, copy the 4 existing items into the newly allocated space and only then add a new item. So, if you know ahead of time how many items you'll be adding to a list (or even if you only know a theoretical upper bound), you should construct the list using that known capacity. This will speed up the process of adding many items to a single list.
5. Don't know how crypto providers work, but since this part of your algorithm does not depend on cp.Count or the magnitude of populationCount, it doesn't matter for the big-O complexity metric.

Permalink Reply by David Rutten on June 13, 2017 at 9:34am

There's no such thing as O(13). O(1) is a stand-in for constant time, no matter how long it takes. O(1) tells you that it always takes the same amount of time, but it doesn't tell you how much time. Similarly, O(2N) is not meaningful, because it merely linearly scales the actual measured runtime, which is not what big-O notation is about.

Initialising new empty collections is almost always an O(1) operation. It's only when you initialise a class and populate it through the constructor that complexity may be worse. For example new HashSet<int>(largeIntegerCollection) or new SortedList<string, int>(largeDictionary). Note that the comments for the latter constructor on MSDN specifica....

Permalink Reply by David Rutten on June 13, 2017 at 9:35am

You mean I should do something like: List<Point3d> test = new List<Point3d>(N); if I know I am going to have N points in the list. 

Yup.

Permalink Reply by David Rutten on June 13, 2017 at 9:36am

So <calculateFitness> has runtime N^2 and <List.ToList()> runtime N. What is then the total runtime? 

Either O(N+N²) or just O(N²) depending on opinion. I'd say the latter.