Question: Let T be an arbitrary binary tree with n nodes. For each node x in T let us define f(x) as the logarithm of the

Let T be an arbitrary binary tree with n nodes. For each node x in T let us define f(x) as the logarithm of the number of descendants of x, including x itself. So, f(x) is log n if x is the root and it is O if x is a leaf node in T. Now let us define F(T) to be the sum of f(x) over all nodes x in T. We want to determine tight asymptotic lower and upper bounds on F(T) based on the structural shape of T. These bounds can be expressed as functions of n. F(T) can be as low as LB(n) = 0(?) and as high as UB(n) = (?). O a. LB(n) = (n log n) and UB(n) = 0(n). O b. LB(n) = (log n) and UB(n) = O(n). OcLB(n) = O(n) and UB(n) = (n). O d. LB(n) = 0(n) and UB(n) = (n log n)
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
