1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Anastaziya [24]
3 years ago
11

Suppose that, even unrealistically, we are to search a list of 700 million items using Binary Search, Recursive (Algorithm 2.1).

What is the maximum number of comparisons that this algorithm must perform before finding a given item or concluding that it is not in the list
"Suppose that, in a divide-and-conquer algorithm, we always divide an instance of size n of a problem into n subinstances of size n/3, and the dividing and combining steps take linear time. Write a recurrence equation for the running time T(n), and solve this recurrence equation for T(n). Show your solution in order notation."

Computers and Technology
1 answer:
damaskus [11]3 years ago
7 0

Answer:

There is also an attachment below

Explanation:

Since we are talking about binary search, let's assume that the items are sorted according to some criteria.

Time complexity of binary search is O(logN) in worst case, best case and average case as well. That means it can search for an item in Log N time where N is size of the input. Here problem talks about the item not getting found. So, this is a worst case scenario. Even in this case, binary search runs in O(logN) time.

N = 700000000.

So, number of comparisions can be log(N) = 29.3 = 29.

So, in the worst case it does comparisions 29 times

You might be interested in
Viktor has climbed a tall tree to get a good view of the giraffes on the savannah. He is snapping lots of photographs of the gir
igomit [66]

Answer: C. a good vantage point

3 0
3 years ago
Value: 3
Citrus2011 [14]

Answer:

B - A word is correctly spelled but is used incorrectly in a document

4 0
3 years ago
Which tab in Microsoft Word provides access to the backstage view?
ivann1987 [24]
The answer is control windows
6 0
3 years ago
Read 2 more answers
What are some industries of aerodynamics and hydrodynamics? explain each one in detail.
maria [59]
Aerodynamic- Wind turbine, computational fluid dynamics, and Wind power

Hydrodynamics- Computational Fluid Dynamics, Hydraulics, and Microfluidics
3 0
2 years ago
Read 2 more answers
An anchor is a part of the web page that contains a hyperlink True or False
Wewaii [24]

Answer:

true

Explanation:

5 0
2 years ago
Other questions:
  • ___ refers to all aspects of managing and processing information using computers and computer networks
    13·1 answer
  • What are 3 websites that talk about density of different gases, density in air, behavior of different gases of earth, convection
    13·1 answer
  • A __________ network is good for connecting computers over boundaries.
    6·2 answers
  • What is the internet?
    5·2 answers
  • Which line in the following program contains the header for the showDub function? 1 #include«iostream» 2 using namespace std; 4
    15·1 answer
  • Write a class called (d) Teacher that has just a main method. The main method should construct a GradeBook for a class with two
    7·1 answer
  • What is the name of the symbol that is used to classify and categorize information?​
    10·2 answers
  • Which is an example of an effective study skill?
    11·2 answers
  • Why would an online survey of 2,000 visitors to your college’s Web site be of little use in assessing the neighboring community’
    7·1 answer
  • Each entry in a linked list is called a_______
    11·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!