CODEWITHSUNDEEP
algorithmdata-structurestime-complexity
user12480076
user12480076

Reputation:

What is the Time-Complexity of this function in C?

I'd like to calculate the complexity of this function in C. It's a general tree

struct nodeG {  
  int key;
  struct nodeG *left_child;
  struct nodeG *right_sib;
};

int aux (NodeG u) {
    int current = 1;                                                // O(1)
    int childs = 0;                                                 // O(1)
    while (u) {                                                     // O(k)
        if (u-> left_child)                                         // O(1)
            childs += aux (u-> left_child);                         // O(1)
        if (u->right_sib && current && u->key < u->right_sib->key)  // O(1)
            current = 0;                                            // O(1)
        u = u -> right_sib;                                         // O(1)
    }
    return current + childs;                                        // O(1)
}

Upvotes: 3

Views: 57

Answers (1)

interjay
interjay

Reputation: 110108

Taking into account all the recursive calls, the function performs O(1) operations on each node in the tree, so the total runtime is O(n) where n is the number of nodes.

In more detail, the function is called once for the leftmost child of each node. The while loop then loops over all its siblings. So the interior of the loop is executed once per node, or a total of n times. Other than the loop and the recursive call, the remaining statements are all O(1). So this ends up taking O(n) time.

Upvotes: 0

Related Questions