Algorithm complexity in online test

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;
}

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(n²)
• When reverseOrder is false: O(n²)

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.

Answer 1

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