Computational complexity of a algorithm

Question

Algorithm 1. STACKSTUFF(n)
Input: Integer n
1) Let S = an empty Stack
2) Let X = -1
3) For i = 1 to 2n
4) S.Push(i)
5) End For
6) For i = 1 to n
7) Let X = S.Pop()
8) End For
Output: The contents of X

---

1) What is this algorithm written in pseudo code doing? 

To my understanding, S.Push(i) adds item i on top of stack S. X = S.Pop() removes the item from the top of stack S and assigns it to X.

2) What is the computational complexity O(n) for algorithm 1, STACKSTUFF?

I believe the answer would be: O(3n)

The first loop would be 2n and the second for loop n, so 2n+n=3n.

Or... Would the answer just be O(n^2) since all we would have to do would be n*n?

3) If n > 0 then what is returned by the algorithm? What about n < 1

a) 2n
b) -1
c) n-1
d) n+1
e) None of the above

This last bit really confuses me. From my understanding, if n was always greater than 0, the algorithm would always return n+1, and if n was always less than 1, the algorithm would return n-1. However this is pure guess work...

If I thought about this logically, then let's say n was 3 for example. Since the first For loop is 1 to 2n, then this would mean that we would end up with the following stack S={1,2,3,4,5,6} as it added every number up to double n into S. The second For loop then pops 3 numbers so X ends up looking like this X={6,5,4}. If I am correct there... Should I assume that this was just a trick question and the answer is e, none of the above?

I just wanted to make sure my understanding here was correct before I continued studying. Thanks for any help.

Answer 1

1) The algoritm adds 1..2n to a stack, then pops n elements. Meaning that 1..n is left in the stack and the last popped element remains in X.

2) You are correct. The algoritm has complexity: 2 + (2n * 1) + (n * 1) = 3n + 2 = O(3n) = O(n).

3) The algoritm as storing the last popped element in X and then returning X and the last popped element is n + 1, so the answer should be d) n+1.

EDIT

Explanation on 3:

if n > 0:

X := -1
push 2n to the stack
stack = {1, 2, .. n, n + 1, ..., 2n}
pop n elements from the stack and store the popped element in X
first iteration:
   X := stack.pop()
   stack = {1, 2, .. n, n + 1, ..., 2n - 1}
   X = 2n
... until we have popen n numbers. 
stack = {1, 2, .. n}
X = n + 1

if n < 1

X := -1
because n < 1 we won't do any iterations in the loops
so X will not change and still be -1