Please read the new rule regarding the restriction on the use of AI tools. ×

Gajanana's blog

By Gajanana, history, 13 months ago, In English

Is Time Complexity O(N), O(2N) or something else, why?

Please tell me space complexity also for this.

   bool solve(Node *root1, Node *root2)
    {
        if(root1 == NULL && root2 == NULL)
            return true;

        if((root1 == NULL) || (root2 == NULL))
            return false;

        if(root1->data != root2->data)
            return false;

        bool v1 = myfunc(root1->left, root2->left);
        bool v2 = myfunc(root1->left, root2->right);
        bool v3 = myfunc(root1->right, root2->right);
        bool v4 = myfunc(root1->right, root2->left);

        return (v1 & v3) | (v2 & v4);
    }

    
    bool isIsomorphic(Node *root1, Node *root2)
    {
        return solve(root1, root2);
    }
  • Vote: I like it
  • +10
  • Vote: I do not like it

| Write comment?
»
13 months ago, # |
  Vote: I like it +11 Vote: I do not like it

$$$O(N)$$$ and $$$O(2N)$$$ is the same thing — you should read-up on big-O notation.

Assuming no special tree properties, this particular code is quadratic and has time complexity of $$$O(N^2)$$$. There are several ways to derive this — the simplest is likely to consider that for every level of the trees, each pair of one node from the first and one node from the second will be checked.