CODEWITHSUNDEEP
complexity-theorytime-complexity
dead programmer
dead programmer

Reputation: 4375

complexity for recursion function

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

Answers (1)

rnbguy
rnbguy

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

Related Questions