Stacks and time

I wrote the push and pop operations for my stack. I'm trying to figure out what the worst case time complextiy is using asymptotic notation for these two operations is......i'm guessing Big O(log n)?..but i'm not sure..

Code:

---


void stack::push(int x){

  if(size < 3){
    top++;
    stackArray[size] = x;
    size++;


  }
}

int stack::pop(){

  int x = stackArray[top];
  top--;
  size--;
  return x;



}

---

Considering there are no loops or recursion, and all I see are simple comparisons, increment, assignment, decrement, I'd say the best, average and worst case complexity for both is constant time.

ah..see what you mean. If I added an operation called peek that would look at the next item below the top of the stack... wouldn't that add more steps? How would you figure out the asymptotic time complexity. ...wouldn't it add two more steps?

Quote:

---

If I added an operation called peek that would look at the next item below the top of the stack... wouldn't that add more steps?

---

No matter how large the stack, peek (or pop and push, for that matter) would still take roughly the same number of operations.

hmm... I don't understand

hmm... okay, this is how I might implement the stack operations you mentioned:

Code:

---

void stack::push(int x) {
    // Implemented with fixed size array, so no expansion.
    if (size < MAX_SIZE) {
        stackArray[size] = x;
        ++size;
    }
}

void stack::pop() {
    if (size > 0) {
        --size;
    }
}

int& stack::peek() {
    return stackArray[size - 1];
}

const int& stack::peek() const {
    return stackArray[size - 1];
}

---

Look at push(). Suppose the array has no elements. We know that(size < MAX_SIZE) will be true, hence we have an assignment and an increment. Suppose the array has MAX_SIZE-1 elements. We still have an assignment and an increment. If the array has MAX_SIZE elements, the only operation performed is the comparison. So, the size of the array does not change the complexity of push().

Look at pop(). Suppose the array has no elements. We know that (size > 0) is false, so the only operation is the comparison. Suppose the array has MAX_SIZE elements. (size > 0) is true, so besides the comparison we have a decrement. That's all, so the size of the array does not change the complexity of pop().

For your implementation of pop() this is true as well. It does not matter how large is the array, the same sequence of:

Code:

---

int x = stackArray[top];
top--;
size--;
return x;

---

will be performed.

It is clear that both non-const and const versions of peek() run in constant time since they just access the array by index, and arrays have random access.

wow that really helped me! Thanks alot.. This might be a dumb question but how many steps would it take to perform the peek operation?

Quote:

---

Originally Posted by cjwenigma

how many steps would it take to perform the peek operation?

---

Quote:

---

Originally Posted by laserlight

peek() run in constant time since they just access the array by index, and arrays have random access.

---

as mentioned, for your array implementation of the stack, accessing the first (or last, or any) index of an array is constant time, since you can jump directly to that memory location.

If, on the other hand, you implemented the stack as a linked list, and made a "peek(x)" function that gives you the xth element, this function would be O(n), as you'd have to search through the list to find the xth element.

--
Mats