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
Which of the following statements is true of a server? Question 18 options: A) It supports processing requests from remote compu
TiliK225 [7]

Answer:

Option (A) is the correct answer of this question.

Explanation:

The server supports the processing requests from the remote computers. A system is a device built to accommodate inquiries from many other external systems and customers to execute transactions. Employees are called private computer ,tablets, including phones which connect websites.

Network resources are handled through servers.The server is a software application or tool providing a service to some other software program and its customer, also identified as those of the user.

Other options are incorrect because they are not related to the given scenario.

5 0
3 years ago
A picture of kitchen sink draining system​
ale4655 [162]

Answer: So do you need a picture of that or what do you need exactly i would love to help!!

5 0
3 years ago
Read 2 more answers
What are the basic tasks performed by an operating system?​
Kruka [31]

Answer:

An operating system is a software which performs all the basic tasks like file management, memory management, process management, handling input and output, and controlling peripheral devices such as disk drives and printers.

Explanation:

i hope it helps:)

3 0
2 years ago
Summarize the five stages of cultural shock
Anton [14]
1. Honeymoon stage
2. Distress and anxiety
3. Adjustment
4. Adaption
5. Re-entry shock
8 0
3 years ago
Read 2 more answers
What is the size of the key space if all 8 characters are randomly chosen 8-bit ascii characters?
Slav-nsk [51]
21...............................
4 0
3 years ago
Other questions:
  • What is the f(n) runtime of the following pseudocode: sum-0 for A = N/2 downto 1 for B-1 t increment sum by B Explain: exactly w
    13·1 answer
  • A(n) _____ is a type of man-in-the-middle attack where an attacker captures the data that is being transmitted, records it, and
    15·2 answers
  • 2. What are the pros and cons of Toyota structure?
    13·1 answer
  • Create a view named product_summary. This view should return summary information about each product. Each row should include pro
    13·1 answer
  • Dorothy needs to edit JPEG and GIF files in a multimedia application. Which software can Dorothy use to edit these files?
    8·2 answers
  • Primary technology skills are skills that are necessary for success in online education
    9·2 answers
  • How are computers 35 years ago and how are they presently and how are they going to be in the next 35 years
    9·1 answer
  • Which component of a word processor displays the name of the document?
    13·1 answer
  • Which printer are used to print text and graphics with high speed ​
    15·1 answer
  • Can able to Computer decide its input by itself? How ?​
    15·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!