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.
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.
Explanation on 3:
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
X := -1
because n < 1 we won't do any iterations in the loops
so X will not change and still be -1