We compare the speed of searching a B-tree with a standard binary search tree (BST). If...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
We compare the speed of searching a B-tree with a standard binary search tree (BST). If there are n keys, let TBfree (n) and TBST(n) denote their worst case search times. We write TBST(n) = lgn, measured in some idealized time unit. NOTE: each time unit is less than e machine cycles for some moderate constant c> 1 (most likely, c < 40). A B-tree with n leaves has height at most loggn for some constant B2 2. Each internal node is stored in a disc block, and assume that the time to read or write a disc block is 1000 time units. In the search algorithm, assume that we read and write one disc block per level. Moreover, assume that it takes lg B time units to find the correct child in the next level of the search. (a) Write an expression for TBtree(n). (b) What is TBtree (nº) when n = 10° is 1 billion, and B = 500? Use the "Computer Science approximation of "Ig", e.g., Ig 1000 = 10, and lg 10º = 30. (c) Comparing TBST (n) and TBtree (n), my student Sharp exclaimed: we should NEVER use B-trees! If Mr.Sharp right, then it is a paradox to say that B-trees are very important! Explain this paradox. We compare the speed of searching a B-tree with a standard binary search tree (BST). If there are n keys, let TBfree (n) and TBST(n) denote their worst case search times. We write TBST(n) = lgn, measured in some idealized time unit. NOTE: each time unit is less than e machine cycles for some moderate constant c> 1 (most likely, c < 40). A B-tree with n leaves has height at most loggn for some constant B2 2. Each internal node is stored in a disc block, and assume that the time to read or write a disc block is 1000 time units. In the search algorithm, assume that we read and write one disc block per level. Moreover, assume that it takes lg B time units to find the correct child in the next level of the search. (a) Write an expression for TBtree(n). (b) What is TBtree (nº) when n = 10° is 1 billion, and B = 500? Use the "Computer Science approximation of "lg", e.g., Ig 1000 = 10, and lg 10⁰ = 30. (c) Comparing TBST (n) and TBtree (n), my student Sharp exclaimed: we should NEVER use B-trees! If Mr.Sharp right, then it is a paradox to say that B-trees are very important! Explain this paradox. We compare the speed of searching a B-tree with a standard binary search tree (BST). If there are n keys, let TBfree (n) and TBST(n) denote their worst case search times. We write TBST(n) = lgn, measured in some idealized time unit. NOTE: each time unit is less than e machine cycles for some moderate constant c> 1 (most likely, c < 40). A B-tree with n leaves has height at most loggn for some constant B2 2. Each internal node is stored in a disc block, and assume that the time to read or write a disc block is 1000 time units. In the search algorithm, assume that we read and write one disc block per level. Moreover, assume that it takes lg B time units to find the correct child in the next level of the search. (a) Write an expression for TBtree(n). (b) What is TBtree (nº) when n = 10° is 1 billion, and B = 500? Use the "Computer Science approximation of "Ig", e.g., Ig 1000 = 10, and lg 10º = 30. (c) Comparing TBST (n) and TBtree (n), my student Sharp exclaimed: we should NEVER use B-trees! If Mr.Sharp right, then it is a paradox to say that B-trees are very important! Explain this paradox. We compare the speed of searching a B-tree with a standard binary search tree (BST). If there are n keys, let TBfree (n) and TBST(n) denote their worst case search times. We write TBST(n) = lgn, measured in some idealized time unit. NOTE: each time unit is less than e machine cycles for some moderate constant c> 1 (most likely, c < 40). A B-tree with n leaves has height at most loggn for some constant B2 2. Each internal node is stored in a disc block, and assume that the time to read or write a disc block is 1000 time units. In the search algorithm, assume that we read and write one disc block per level. Moreover, assume that it takes lg B time units to find the correct child in the next level of the search. (a) Write an expression for TBtree(n). (b) What is TBtree (nº) when n = 10° is 1 billion, and B = 500? Use the "Computer Science approximation of "lg", e.g., Ig 1000 = 10, and lg 10⁰ = 30. (c) Comparing TBST (n) and TBtree (n), my student Sharp exclaimed: we should NEVER use B-trees! If Mr.Sharp right, then it is a paradox to say that B-trees are very important! Explain this paradox.
Expert Answer:
Answer rating: 100% (QA)
On the basis of the result one can say that we should never use the Btree But what will that person ... View the full answer
Related Book For
Modeling the Dynamics of Life Calculus and Probability for Life Scientists
ISBN: 978-0840064189
3rd edition
Authors: Frederick R. Adler
Posted Date:
Students also viewed these programming questions
-
Provide 3 examples from your life of a "need. "What are SMART goals and why are they important as they relate toyour financial goals and any goal you may set now or in the future? What did you learn...
-
For the following, calculate the NPV. Investment amount: ($100,000). Cash flows: Yr1: 25,000 Yr2: 38,000 Yr3: 44,000 Yr4: 28,000. Cost of capital: 15%
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
Four hospitals located in one county are cooperating to establish a centralized blood-bank facility to serve them all. On an xy coordinate grid of the county, the hospitals are found at the following...
-
Sanyo produces audio and video consumer goods and exports a large fraction of its output to the United States under its own name and the Fisher brand name. It prices its products in yen, meaning that...
-
HMT, already in the business of marketing agricultural products, decided to try its hand at marketing potatoes for processing. Nine months before the potato harvest, HMT contracted to supply Bell...
-
The following summarised information relates to the Pagg group of companies. \section*{Additional information:} 1 Pagg acquired its shareholding in Ragg Ltd on 1 April 19X5. Ragg's profit and loss...
-
C-Cell Wireless needed additional capital to expand, so the business incorporated. The charter from the state of Georgia authorizes C-Cell to issue 50,000 shares of 7%, $50 par value cumulative...
-
Wildhorse Ltd. purchased a delivery truck on January 1, 2021, at a cost of $74,080. The truck is expected to have a residual value of $8,490 at the end of its 4-year useful life. Wildhorse has a...
-
Midwest Mills has a plant that can mill wheat grain into a cracked wheat cereal and then further mill the cracked wheat into fl our. The company can sell all the cracked wheat cereal that it can...
-
Project B: % c. If the WACC was 5% and A and B were mutually exclusive, which project would you choose? (Hint: The crossover rate is 26.71%.) -Select- If the WACC was 10% and A and B were mutually...
-
In 2002, a gargantuan iceberg broke away from the Ross Ice Sheet in Antarctica. It was approximately a rectangle with dimensions 218 km long, 25.0 km wide, and 250.0 m thick. What is the mass of this...
-
Island Novelties, Inc., of Palau makes two products, Hawaiian Fantasy and Tahitian Joy. Present revenue, cost, and sales data for the two products follow: Selling price per unit .. Variable expenses...
-
Suppose the following recurrence relation is given: tn - -6-tn-1 +8tr-2 = 0 Restate this recurrence as a characteristic equation. Then, find the roots of this equation. Now, assume (for some initial...
-
8. [20 points] firm makes a product (product A) from five components (intermediate Items B, D, and E, and purchased item C). The bill of materials (BOM) of product A shows the required number of sub-...
-
How do allosteric enzymes function in the context of metabolic pathways, and what are the implications of their regulatory roles in cellular metabolism ? Explain
-
Trade-ins. You may have heard advertisements from car dealerships that say something like "Bring in your car, paid for or not, and we'll take it as a trade-in for a new car." The advertisement does...
-
What is a content filter? Where is it placed in the network to gain the best result for the organization?
-
Find and graph the solutions of the following discrete-time dynamical systems for five steps with the given initial condition. Compare the graph of the solution with the graph of the updating...
-
The sample space is S = {0, 1, 2, 3, 4). Suppose that Pr({0}) = 0.2 Pr({1}) = 0.3 Pr({2}) = 0.4 Pr({3}) = 0.1 Pr({4}) = 0.0. Find Pr(A) and Pr(Ac) if A = {0, 1, 2} and Pr(B) if B = {0, 2, 4}. Is Pr(A...
-
What is the genotype at the eye color locus in the first generation? Often geneticists want to change one allele in an out-crossing organism while keeping the rest of the genome the same. For...
-
U.S. Industries has a subsidiary in Switzerland. The subsidiary's financial statements are maintained in Swiss francs (CHF). Exchange rates (\($/CHF)\) for selected dates are as follows: The...
-
Asda is a British supermarket chain owned by Wal-Mart Stores, Inc. Assume that the following data relate to Asda's activities for 2017 (in millions).. Exchange rates (\($/)\) during 2017 are:...
-
Massmart Holdings Ltd. is a South African subsidiary of Wal-Mart Inc., selling high volume, low margin branded consumer goods to customers in twelve countries in Africa. Massmart's accounts are...
Study smarter with the SolutionInn App