Use an argument similar to that given in Section 7.9 to prove that log n is a
Question:
Use an argument similar to that given in Section 7.9 to prove that log n is a worst-case lower bound for the problem of searching for a given value in a sorted array containing n elements.
Transcribed Image Text:
7.9 Lower Bounds for Sorting This book contains many analyses for algorithms. These analyses generally define the upper and lower bounds for algorithms in their worst and average cases. For most of the algorithms presented so far, analysis is easy. This section considers a more difficult task an analysis for the cost of a problem as opposed to an algorithm. The upper bound for a problem can be defined as the asymptotic cost of the fastest known algorithm. The lower bound defines the best possible efficiency for any algorithm that solves the problem, including algorithms not yet invented. Once the upper and lower bounds for the problem meet, we know that no future algorithm can possibly be (asymptotically) more efficient. A simple estimate for a problem's lower bound can be obtained by measuring the size of the input that must be read and the output that must be written. Certainly no algorithm can be more efficient than the problem's I/O time. From this we see that the sorting problem cannot be solved by any algorithm in less than 2(n) time because it takes at least n steps to read and write the n values to be sorted. Based on our current knowledge of sorting algorithms and the size of the input, we know that the problem of sorting is bounded by f(n) and O(n log n).
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 100% (1 review)
Consider the problem of searching for a given value in a sorted array In the worst case the value ma...View the full answer
Answered By
GERALD KAMAU
non-plagiarism work, timely work and A++ work
4.40+
6+ Reviews
11+ Question Solved
Related Book For
Practical Introduction To Data Structures And Algorithm Analysis Java Edition
ISBN: 9780136609117
1st Edition
Authors: Clifford A. Shaffer
Question Posted:
Students also viewed these Computer science questions
-
Prove that the first test in Theorem 11.3.4 does indeed have level 0. Hint: Use an argument similar to that used to prove part (ii) of Theorem 9.5.1.
-
Case Study: Quick Fix Dental Practice Technology requirements Application must be built using Visual Studio 2019 or Visual Studio 2017, professional or enterprise. The community edition is not...
-
In Corollary 10.2 we were concerned with finding the appropriate "big-Oh" form for a function f: Z+ R+ U {0} where f(1) ¤ c, for c Z+ f(n) ¤ af (n / b) + c, for a, b Z+ with b ¥ 2,...
-
Refer to the table for Moola at the bottom of this page to answer the following questions. What is the equilibrium interest rate in Moola? What is the level of investment at the equilibrium interest...
-
A mass m is attached to the end of a spring with spring constant k on a frictionless horizontal surface. The mass moves in circular motion of radius R and period T. Due to the centrifugal force, the...
-
A HartreeFock calculation using the minimal basis set of the 1s, 2s, 2p x , 2p y , and 2p z AOs on each of N and O generated the energy eigenvalues and AO coefficients listed in the following table....
-
Environmental compliance: a market opportunity. Table 2.1 shows estimates of the size of the market for environmental technologies and services needed to comply with environmental standards. In 1996...
-
The following is net asset information for the Dhillon Division of Klaus, Inc.: The purpose of the Dhillon Division (also identified as a reporting unit or cash-generating unit) is to develop a...
-
Identify what process you would use to craft a marketing message that would be specially tailored to the employee stakeholder group to aid in recruiting top candidates. Include information on...
-
One possible improvement for Bubble Sort would be to add a flag variable and a test that determines if an exchange was made during the current iteration. If no exchange was made, then the list is...
-
Counting sort (assuming the input key values are integers in the range 0 to m - 1) works by counting the number of records with each key value in the first pass, and then uses this information to...
-
Consider the budgeting problem for the General Foundry project as described in Section 7.5, using the information provided in Table 7.4. Suppose that cash flow is a big concern for the project...
-
HELLO Inc. is small company that manufactures and distributes toys for children. The company has estimated the following figures for the coming year: Sales Average receivables Gross profit margin...
-
Find a degree 3 polynomial whose coefficient of x^(3) is equal to 1. The zeros of this polynomial are 33, -41, and 4i. Simplify your answer so that it has only real numbers as coefficients. 2. The...
-
What reward mechanisms can an organization develop and introduce to attract, recruit, select, and retain qualified talent to fill overseas posts? Provide practical examples and related facts to...
-
In a large organizations with many businesses, a marketing plan with marketing objectives to increase sales and marketing share is usually done at what level? Explain.
-
The input-output relationships of two filters are described by (i) y[n] = -0.9 y[n- 1] + x[n] and (ii) y[n] = 0.9 y[n 1] + x[n]. For both cases, determine expressions for the system function H(z) and...
-
What is the difference between an ideal standard and an attainable standard?
-
Coastal Refining Company operates a refinery with a distillation capacity of 12,000 barrels per day. As a new member of Coastal's management team, you have been given the task of developing a...
-
Implement the containKey(k) method, as described in Exercise R-10.3, for the SortedTableClass.
-
Consider lines 3133 of Code Fragment 10.8 in our implementation of the class ChainHashMap. We use the difference in the size of a secondary bucket before and after a call to bucket.remove(k) to...
-
Modify the Pair class from Code Fragment 2.17 on page 92 so that it provides a natural definition for both the equals( ) and hashCode( ) methods.
-
Consider a pendulum with a bob of mass m that is suspended from a spring rather than a rigid rod. Assume that the spring has spring constant k, that it has negligible rest length and mass (that is,...
-
Calculate the fraction per m of 9.3 MeV alpha particles scattered at 60 from a gold foil of thickness 3.2 x 107 m at a distance of 1.5 cm from the target. Round to two sig figs.
-
1. The following diagram shows a glancing collision of mass 1 and mass 2. Assume that the masses are the same and the surface has no friction. Before Collision After Collision horizontal axis Mass 2...
Study smarter with the SolutionInn App