I want to know the time complexity of this algorithm which is used to sort a stack using another stack. I thought it is O(N^2) but apparently it looks more than that.
public static Stack<Integer> sort(Stack<Integer> s) {
Stack<Integer> r = new Stack<Integer>();
while(!s.isEmpty()) {
int tmp = s.pop();
while(!r.isEmpty() && r.peek() > tmp) {
s.push(r.pop());
}
r.push(tmp);
}
return r;
}
If sorting stack [x_2, .., x_n]
(stack grows towards right) takes t(n-1)
time, sorting stack [x_1, .., x_n]
time will do the following
[x_2, .., x_n]
of s
x_1
to tmp
n-1
elements from r
to s
x_1
to r
So running the algorithm on [x_1, .., x_n]
will take at most t(n-1) + O(n)
time. That leads to (for some constant c
)
t(n) <= O(n) + t(n-1) <= c * n + t(n-1)
t(n) <= c * n + c * (n - 1) + t(n-2) <= ... <= c * (1 + 2 + ... + n)
t(n) <= c * n(n + 1) / 2
So t(n)
is O(n^2)
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With