What is the running time of your size() operation assuming there are N elements
ID: 3886748 • Letter: W
Question
What is the running time of your size() operation assuming there are N elements in the stack when size() is invoked. Express you answer using asymptotic notation:
Class Stack {
public int count = -1; //default
pop() { //pop operations
this.count--; //decrementing count
}
push(obj) { //push operations
this.count++; //incrementing the value
}
isEmpty() {
if(this.count == 1)
empty;
}
}
Compare the eciency of this new version of size() with this that uses the internal variable t:
Which one is more ecient?
Explanation / Answer
The complexity of the size operation is of order O(1) irrespective of N as it just returns the value of count+1. The other implementation of size is also same as the current implemementation as both are initializes to -1 at the start and both need similar processing. However the isEmpty fumction in the question is not correct, the stack is empty if count = -1 and not 1
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.