Question 9571 – Time-Complexity
February 13, 2024Question 10668 – Time-Complexity
February 13, 2024Question 9573 – Time-Complexity
A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x} then the worst-case time complexity of the program is
Correct Answer: B
Question 23 Explanation:
Contains a balanced binary search tree.
⇒ g(x) = min (no. of leaf nodes of left-subtree of x, no. of leaf nodes in the right-subtree of x)
→ Total no. of leaves = n
Time complexity for a binary search = log n
Time complexity of the program is = O(n(log n))
⇒ g(x) = min (no. of leaf nodes of left-subtree of x, no. of leaf nodes in the right-subtree of x)
→ Total no. of leaves = n
Time complexity for a binary search = log n
Time complexity of the program is = O(n(log n))
Θ (n)
Θ (n log n)
Θ (n2)
Θ (n2 log n)
Subscribe
Login
0 Comments