CODEWITHSUNDEEP
recursiontime-complexity
msdev
msdev

Reputation: 63

Time complexity of reversing a stack with recursion

I have tried to find the time complexity of the following code.

int insert_at_bottom(int x, stack st) {
if(st is empty) {
    st.push(x)
}
else {
    int a = st.top()
    st.pop()
    insert_at_bottom(x)
    st.push(a)
}
}
void reverse(stack st) {
    if(st is not empty) {
        int st = st.top()
        st.pop()
        reverse(st)
        insert_at_bottom(x, st)
    }
}
// driver function
int[] reverseStack(int[] st) {
    reverse(st)
    return st
}

For each element on top of the stack we are popping the whole stack out placing that top element at the bottom which takes O(n) operations. And these O(n) operations are performed for every element in the stack, so time complexity should be O(n^2).

However, I want to find the time complexity mathematically. I tried to find the recurrence relation, and I got T(n)=2T(n-1)+1. This is probably wrong, as the time complexity of the second function call should not be taken as T(n-1).

Upvotes: 1

Views: 172

Answers (1)

Berthur
Berthur

Reputation: 4495

Your argumentation is in general correct. If insertion at the bottom takes O(n) time, then the reverse function takes O(n2) time, because it performs a linear-time operation on the stack for each element.

The recurrence relation for reverse() would look a bit different though. In each step, you do three things:

  1. Call itself on n-1
  2. An O(n) time operation (insert_at_bottom())
  3. Some constant-time stuff

Thus, you can just sum these together. So I would argue it can be written as:

T(n) = T(n-1) + n + c, where c is a constant.

You will find that, due to recursion, T(n-1) = T(n-2) + n-1 + c. So, if you keep expanding the whole series in this fashion under n > 0, you obtain:

T(n) = 1 + ... + n-1 + n + nc

Since 1 + 2 + ... + n) = n(n + 1)/2 (see this), we obtain that

T(n) = n(n+1)/2 + nc = n2/2 + n/2 + nc = O(n2). □

The O(n) time of insert_at_bottom(), you can show in a similar way.

Upvotes: 1

Related Questions