int size(Node* root){
    if (root == nullptr) {
        return 0;
    }
    return size(root->left)   1   size(root->right);
}
bool isBST(Node* node, int min, int max)
{
    if (node == nullptr) {
        return true;
    }
    if (node->data < min || node->data > max) {
        return false;
    }
    return isBST(node->left, min, node->data) &&
        isBST(node->right, node->data, max);
}
int findLargestBST(Node* root)
{
    if (isBST(root, INT_MIN, INT_MAX)) {
        return size(root);
    }
 
    return max(findLargestBST(root->left), findLargestBST(root->right));
}
 

This is a code to find largest bst in a binary tree. So according to this post the worst case time complexity of brute force solution is O(n^2) but how? It should be O(n^3) no ? since we are passing size function also

CodePudding user response：

The size function is only ever used once and is O(n). So the complexity is O(n^2 n) == O(n^2).

Update: Let me rephrase this as my reasoning wasn't clear at all.

The size function gets called many times. Either because a tree is BST or somewhere down there for each subtree when findLargestBST is called with each subtree. The size function also gets called recursively by size itself.

But for each node size is called at most once. So accumulated it is O(n). To see this you have to look at the two cases in findLargestBST.

If the tree is BST then size gets called for the whole tree and internally recurses to each element of the tree.

If the tree is not BST then the tree is split and size can be called for each subtree. But at most that looks at each element in the left tree and each element in the right tree. The two (or more) calls to size can never overlap and look at an element more than once.

Accumulated that is O(n).