Reputation: 4375
I have written a function for reverse a stack inline. these two are member function of stack class .
void reverse()
{
int first=pop();
if(first!=-1)
{
reverse();
insert(first);
}
}
private:
void insert(int i)
{
int temp=pop();
if(temp==-1)
{
push(i);
}
else
{
/* there is already a element in the stack*/
insert(i);
push(temp);
}
}
Now how can i analyze my function in form of big O to calculate complexity.
Upvotes: 0
Views: 331
Reputation: 1399
Your insert()
takes O(length of the stack)
time because:
T(n) = T(n-1) + O(1)[to push] = O(n)
and your reverse()
takes O(square of the length of the stack)
time because:
T(n) = T(n-1) + O(n)[for insert] = O(n^2)
Upvotes: 1