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
Write a program that asks the user how many numbers will be entered and then has the user enter those numbers. When this is done
KATRIN_1 [288]

Answer:

<em>The program written in Python 3 is as follows;</em>

<em>The program does not make use of comments; however, see explanation section for detailed line by line explanation of the program</em>

num = int(input("Number of Inputs: "))

mylist = []

userinput = int(input("Enter a digit: "))

i = 1

while i < num:

     mylist.append(userinput)

     userinput = int(input("Enter a digit: "))

     i += 1

   

try:

     first7 = mylist.index(7)+1

     print('The first position of 7 is ',first7)

     last7 = num - 1 - mylist[::-1].index(7)

     print('The last position of 7 is ',last7)

except:

     print('7 is not on the list')

Explanation:

This line prompts user for the number of inputs

num = int(input("Number of Inputs: "))

This line declares an empty list

mylist = []

This line inputs the first number into the empty list

userinput = int(input("Enter a digit: "))

The italicized lines represent an iteration that allows user to input the numbers into the empty list.

<em>i = 1</em>

<em>while i < num:</em>

<em>      mylist.append(userinput)</em>

<em>      userinput = int(input("Enter a digit: "))</em>

<em>      i += 1</em>

The try-except is used to check the presence of 7 in the list

try:

This checks the first occurrence of 7

     first7 = mylist.index(7)+1

This prints the first occurrence of 7

     print('The first position of 7 is ',first7)

This checks the last occurrence of 7

     last7 = num - 1 - mylist[::-1].index(7)

This prints the last occurrence of 7

     print('The last position of 7 is ',last7)

The following is executed if there's no occurrence of 7

except:

     print('7 is not on the list')

See Attachments for sample runs

7 0
2 years ago
A system administrator needs to create a high-performance SQL server. What type of disk configuration will allow the administrat
Studentka2010 [4]

Answer:

Pass-through disk

Explanation:

Pass-through disk configuration will allow the administrator to connect an offline physical disk that is connected to the host machine to a VM to maximize a VM's performance.

VMs access a physical hard disk by way of a "pass-through disk," a special virtual disk that directly accesses the physical disk if it is made exclusively available to the VM.

A pass-through disk must be offline in the parent partition of the Hyper-V server.

4 0
3 years ago
Which is not a proper statement?
kodGreya [7K]

Answer:

leftisBlocked()

Explanation:

4 0
2 years ago
Read 2 more answers
Which of the following describes the IP address of a router to which packets destined for a remote network should be sent by def
Elena-2011 [213]

The term that describes the IP address of a router to which packets destined for a remote network should be sent by default is the a gateway of last resort.

<h3>What is 'Gateway Of Last Resort'? </h3>

A Gateway of Last Resort is known to be the Default gateway and this is said to be a route that is known to be often used by the router if no other known route is seen to transmit the IP packet.

Note that Known routes are seen in the routing table. but, any route not known by the routing table is said or known to be forwarded to the default route.

Hence the primary function of a router is so that it can forward packets toward a given destination.

Therefore, The term that describes the IP address of a router to which packets destined for a remote network should be sent by default is the a gateway of last resort.

Learn more about IP address from

brainly.com/question/24930846

#SPJ1

3 0
1 year ago
Which of the following enable unauthorized access to your network, and by extension, the sensitive documents, proprietary code,
oksano4ka [1.4K]

Answer:

(a) Weak passwords

Explanation:

Typically, a password is weak if it is easily discovered by all persons including unauthorized users. When passwords to a network are weak, the network is vulnerable to unauthorized access and may permit access to proprietary code, accounting files and other sensitive documents in the network.

Examples of weak passwords are;

i. those generated from the name of a user.

ii. those generated for a user by default.

iii. those generated from words from dictionary or other similar materials.

iv. those that don't include a combination of letters and numbers and even symbols.

v. those that are short in length e.g less than 8 characters.

3 0
3 years ago
Read 2 more answers
Other questions:
  • When you include a word cover page in a multi page document, the cover page is not considered the first page. True or false?
    13·1 answer
  • A computer has a memory ________, rather than just a single memory component. The lowest level is some form of ________ storage
    11·1 answer
  • One of the major advantages of digital photography is the ability to see the shot as soon as you take it.
    13·1 answer
  • What is the letter for the trash directory on windows 10?
    13·2 answers
  • How would you build a robot
    7·2 answers
  • The ________ view in access looks similar to an excel spreadsheet.
    5·1 answer
  • What do you like and dislike about school? ANDWER FAST!!!
    5·2 answers
  • What are some best practices for file management
    8·1 answer
  • Read the attached paper titled A Survey of Coarse-Grained Reconfigurable Architecture and comment on it. Make sure to specifical
    5·1 answer
  • __________ is a computer tool for evaluating the risk of exposure to wildfires.
    8·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!