###### Question 9571 – Time-Complexity

February 13, 2024###### Question 10668 – Time-Complexity

February 13, 2024# Question 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)

Θ (n

^{2})Θ (n

^{2}log n) Subscribe

Login

0 Comments