Short Answers Section 11.3 Trees, Logs, and Time Analysis 12. Suppose that a B-t

Question

Short Answers
Section 11.3
Trees, Logs, and
Time Analysis

12. Suppose that a B-tree is declared so that MAXIMUM (the maximum number of items in a node) is 84. What is the value of MINIMUM (the minimum number of items in a non-root node)?

13. Suppose that a B-tree is declared so that MAXIMUM (the maximum number of items in a node) is 84. Write one clear sentence to describe why each node's data array is set up to hold up to 85 items (one more than MAXIMUM).

14. Suppose that a and b are two positive integers and n is some non-negative number. Write an equation to show the relationship between log base a of n and log base b of n. Give a derivation to show that the relationship is valid.

Explanation / Answer

12. If a B tree is declared so that maximum is 84, this means value of 2*x -1 =84,

where, x is the minimum number of items in a non root node.

So, value of minimum is x= 85/2 = 42 elements

13. The data array is defined one more than maximum as the one element is used to store the number of element currently present in th node.

14 .

(Logn a)/ (Logn b) = Logb a

To derive the equation, consider :

x = loga b

we can wrire it as

ax = b

take log n on both side

xlogn a = logn b

x = (logn b)/(logn a)

put value of x

logb a = (logn b)/(logn a)

Hence proved

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.