Multiple choice

A program takes as input a balanced binary search tree with n leaf modes and computes the value of a function g(x) for each node x . If the cost of computing g(x) is min (number of leaf-nodes in learsubtree of x , number of leaf-nodes in right-subtree of x) then the worst case time complexity of the program is

  1. $\theta$(n)

  2. O(nlogn)

  3. O(n)2

  4. O(2n)
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

The function g(x) calculates for a node x min no. of leaf noes whether in left subtree or right subtree. The for balanced BST. The no. of inner nodes = leaf nodes−1. So this loop will sun for max n-times so complexity is  $\Theta$(n)

Keep practicing — related questions