сложность для функции рекурсии

Question

Я написал функцию для обратного стека inline. эти два являются функциями-членами класса стека.

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); 

    } 
} 

Теперь, как я могу анализировать свою функцию в форме большого О, чтобы рассчитать сложность.

Answer 1

Ваш insert()O(length of the stack) занимает время, потому что:

T(n) = T(n-1) + O(1)[to push] = O(n) 

и ваш reverse()O(square of the length of the stack) занимает время, потому что:

T(n) = T(n-1) + O(n)[for insert] = O(n^2)