Answer:
O(N!), O(2N), O(N2), O(N), O(logN)
Explanation:
N! grows faster than any exponential functions, leave alone polynomials and logarithm. so O( N! ) would be slowest.
2^N would be bigger than N². Any exponential functions are slower than polynomial. So O( 2^N ) is next slowest.
Rest of them should be easier.
N² is slower than N and N is slower than logN as you can check in a graphing calculator.
NOTE: It is just nitpick but big-Oh is not necessary about speed / running time ( many programmers treat it like that anyway ) but rather how the time taken for an algorithm increase as the size of the input increases. Subtle difference.
Yes i would love to help the cause <span />
Answer:
Each time you insert a new node, call the function to adjust the sum.
This method has to be called each time we insert new node to the tree since the sum at all the
parent nodes from the newly inserted node changes when we insert the node.
// toSumTree method will convert the tree into sum tree.
int toSumTree(struct node *node)
{
if(node == NULL)
return 0;
// Store the old value
int old_val = node->data;
// Recursively call for left and right subtrees and store the sum as new value of this node
node->data = toSumTree(node->left) + toSumTree(node->right);
// Return the sum of values of nodes in left and right subtrees and
// old_value of this node
return node->data + old_val;
}
This has the complexity of O(n).
Explanation:
