Please tell me what is the running time complexity! public class ProblemOne { //

Question

Please tell me what is the running time complexity!

public class ProblemOne {
// created stack called "input"
public static Stack<Integer> sort(Stack<Integer> input) {
// created stack called "tempStack"
Stack<Integer> tempStack = new Stack<Integer>();
// "while" loop that organizes the stack in descending order
while (!input.isEmpty()) {
int tmp = input.pop();
while (!tempStack.isEmpty() && tempStack.peek()
> tmp) {
input.push(tempStack.pop());
}
tempStack.push(tmp);
}
return tempStack;
}
//main method begins
public static void main(String[] args) {
{
// create stack called "input"
Stack<Integer> input = new Stack<Integer>();
// add values to the stack
input.add(50);
input.add(2);
input.add(28);
input.add(98);
input.add(78);
input.add(34);
// print stack before sorting
System.out.println("Stack before sorting: " + input);
System.out.println();
// create stack called "tempStack"
Stack<Integer> tempStack = sort(input);
// print stack after sorting
System.out.print("Stack after sorting: [");
// organize the stack in descending order
while (!tempStack.empty()) {
System.out.print(tempStack.pop() + " ");
}
System.out.print("]");
}
}
}

(a) Write a method in Java to sort a stack of n integer numbers, s, in descending order. static Stack sort(Stack s) To implement this method you must use one more auxiliary stack and you should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push, pop, peek, and isEmpty. (b) What is the running time complexity of your method? Justify

Explanation / Answer

Let there are n element which are already in sroted order

Then for every element in stack

we need to push it to temp and we have to compare with all elements in the temp

which means

if for first element we have to comapre with only one element

for second element we have to compare with two elements

for third element we have to compare with three elements

...

for zero elements we have to comapre with n elements

so total comaprisons = 1+2+3+...n = n(n+1)/2 = O(n2)

SO T.c = O(n2)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---