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
In which of the following ways can using test-taking tips help you?
bogdanovich [222]
In my opinion i think it is A
3 0
3 years ago
Disk quotas are set using the ____ console. diskpart disk management mst windows explorer
liraira [26]
<span>Answer: Disk Management Console</span>
8 0
3 years ago
How will I go about conducting the investigation on fake news
Leno4ka [110]

Answer:

You can begin your report, and write about CNN, BBC, or any other liberal news network.

Explanation:

5 0
3 years ago
Which solution eliminates the need for dedicated high-speed WAN connections between sites
s344n2d4d5 [400]

Answer:

running in the 90 s intensifies

Explanation:

4 0
2 years ago
in python i wrote a function where if the user inputs a certain word the function repeats over again, since the function aaks fo
Colt1911 [192]
Check out the counter set
4 0
2 years ago
Other questions:
  • In the movie evacuees, why were the children evacuated from large cities?
    11·1 answer
  • What is processor, memory RAM, cDRAM,DVD RAM,video card​
    9·1 answer
  • Select the correct answer
    11·1 answer
  • While surfing online, Patricia checks her email and reads the latest messages. She then browsers a website and logs in a comment
    8·1 answer
  • Write a Java program that generates a new string by concatenating the reversed substrings of even indexes and odd indexes separa
    5·1 answer
  • What is the cell reference for row 22 and column B? __________<br><br> In excel
    5·1 answer
  • If a student passes off an author’s work as his or her own, the student has
    6·1 answer
  • R6. Suppose N people want to communicate with each of N - 1 other peo- ple using symmetric key encryption. All communication bet
    13·1 answer
  • A source mainly provides <br> from a text or piece of media.
    6·2 answers
  • Given an initialized variable fileName, write a sequence of statements that create a file whose name is given by the variable an
    15·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!