Time-complexity with recursion

Question

Below is an algorithm that find the biggest sum in a triangle. I want to say this algorithm is O(N^2) since the findMax function call can be replaced with a nested for loop looking through each child for each node. However the recursion make me uncertain. So how can I tell the time-complexity of this code with recursion?

int maxValue = 0;

void findMax ( Node * n , int sum ) {

if ( n == NULL ) {

    if ( maxValue < sum ) {

        maxValue = sum ;

    }

    return ;

}

findMax (n - > leftChild , sum + n - > value ) ;

findMax (n - > rightChild , sum + n - > value ) ;
}

Alireza.N · Accepted Answer · 2019-05-29 12:35:40Z

2

int maxValue = 0; // will be executed once so O(1).

void findMax ( Node * n , int sum ) {

if ( n == NULL ) { // Will be executed in every call of function so if considering the function is called C times it is O(C)

    if ( maxValue < sum ) { // will be executed if the previous if is right so O(c')

        maxValue = sum ; // will be exceuted if the previous if is right so O(c')

    }

    return ; // will be executed once so O(1)

}

findMax (n - > leftChild , sum + n - > value ) ; // visiting every left child of each node

findMax (n - > rightChild , sum + n - > value ) ; // visiting every right child of each node 

// so we are visiting every node at least once if we have n node and m connections(edges) between nodes we have:
// O(n+m+C(c'+c'+1))=O(n+m) + O(K)

answered May 29, 2019 at 12:35

Alireza.N

1597 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Time-complexity with recursion

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related