Brent - 3 months ago 19

C# Question

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 {

items.Add(item);

}

}

return items;

}

- 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(n
^{2}) - When reverseOrder is false: O(n
^{2})

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

- is
`Pop()`

`O(1)`

- In the case of being
`reverseOrder`

, an`true`

to the front of the list is made. Since`Insert`

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 :`List<T>`

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

- In the case of being
`reverseOrder`

, an`false`

is made to append an item to the back of the list. Since`Add`

is not given an initial size,`items`

is never less than`Count`

, resulting in a resize, so according to https://msdn.microsoft.com/en-us/library/3wcytfd1(v=vs.110).aspx :`Capacity`

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.

Answer

You need to ask the people who wrote the test. Any answer here would be strictly opinion based, as we don't have the full context, i.e. what would lead the test author to describe the complexity of the algorithm differently than you have.

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.

You don't say what the correct answer is supposed to be, but I would give it as O(N log N).