Brent Brent - 11 months ago 71
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.

My Answer:

  • 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
    times, because it continues until there is no element left to pop off

  • Pop()

  • In the case of
    , an
    to the front of the list is made. Since
    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 :

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

  • In the case of
    , an
    is made to append an item to the back of the list. Since
    is not given an initial size,
    is never less than
    , resulting in a resize, so according to :

    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 Source

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).