Brent - 1 year ago 93
C# Question

# Algorithm complexity in online test

I had to complete an online programming test for an internship, and got a question on complexity analysis. I answered the question and it was marked wrong, and I would just like to understand why, so I can improve.

The Question:

Give the complexity for the following algorithm when reverseOrder is true and when it is false:

``````List<int> stackToList(Stack<int> stack, bool reverseOrder) {
List<int> items = new List<int>();

while (stack.Count > 0) {
int item = stack.Pop();

if (reverseOrder) {
items.Insert(0, item);
} else {
}
}

return items;
}
``````

EDIT: It was multi-choice, and the possible answers were:

• O(1)

• O(nlogn)

• O(n)

• O(n^2)

You could choose one for when reverseOrder is true, and another for when it is false.

• When reverseOrder is true: O(n2)

• When reverseOrder is false: O(n2)

I got to this answer by way of the following:

• The while loop will iterate
`n`
times, because it continues until there is no element left to pop off

• `Pop()`
is
`O(1)`

• In the case of
`reverseOrder`
being
`true`
, an
`Insert`
to the front of the list is made. Since
`List<T>`
is backed by an array, it is dynamically resized and every element is moved up one space, and the element gets inserted at index 0. According to https://msdn.microsoft.com/en-us/library/sey5k5z4(v=vs.110).aspx :

This method is an O(n) operation, where n is Count.

• In the case of
`reverseOrder`
being
`false`
, an
`Add`
is made to append an item to the back of the list. Since
`items`
is not given an initial size,
`Count`
is never less than
`Capacity`
, resulting in a resize, so according to https://msdn.microsoft.com/en-us/library/3wcytfd1(v=vs.110).aspx :

If Count is less than Capacity, this method is an O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.

I am feeling quite discouraged at the moment, since getting this wrong caused my score to plummet, even though I got all the other questions on the test correct.

That said, I would agree with the test author on the `reverseOrder == false` scenario. While it's true that you may incur a resize operation during the call to `Add()`, the resize operation would introduce at worst a `log N` cost, as the new size doubles with each resize.