For each of the following algorithms medicate their worst-case running time complexity using Big-Oh notation, and give a brief (3-4 sentences each) summary of the worst-case running time analysis. (a) Construction of a heap of size n , where the keys are not known in advance.
(b) Selection-sort on a sequence of size n.
(c) Merge-sort on a sequence of size n.
(d) Radix sort on a sequence of n integer keys, each in the range of[ 0, (n^3) -1]
(e) Find an element in a red-black tree that has n distinct keys.

Answers

Answer 1
Answer:

Answer:

Answers explained below

Explanation:

(a) Construction of a heap of size n , where the keys are not known in advance.

Worst Case Time complexity - O(n log n)

Two procedures - build heap, heapify

Build_heap takes O(n) time and heapify takes O(log n) time. Every time when an element is inserted into the heap, it calls heapify procedure.

=> O(n log n)

(b) Selection-sort on a sequence of size n.

Worst Case Time complexity - O(n^2)

Selection sort finds smallest element in an array repeatedly. So in every iteration it picks the minimum element by comparing it with the other unsorted elements in the array.

=> O(n^2)

(c) Merge-sort on a sequence of size n.

Worst Case Time complexity - O(n log n)

Merge sort has two parts - divide and conquer. First the array is divided (takes O(1) time) into two halves and recursively each half is sorted (takes O(log n) time). Then both halves are combines (takes O(n) time).

=> O(n log n)

(d) Radix sort on a sequence of n integer keys, each in the range of[ 0 , (n^3) -1]

Worst Case Time complexity - O (n log b (a))

b - base of the number system, a - largest number in that range, n - elements in array

Radix sort is based on the number of digits present in an element of an array A. If it has 'd' digits, then it'll loop d times.

(e) Find an element in a red-black tree that has n distinct keys.

Worst Case Time complexity - O (log n)

Red-black tree is a self-balancing binary tree => The time taken to insert, delete, search an element in this tree will always be with respect to its height.

=> O(log n)


Related Questions

Which type of error occurred in the following lines of code? >>> print(9 / 0)Traceback (most recent call last): File " ", line 1, in 9/0ZeroDivisionError: division by zeroAnswer choices:reserved word errorlogical errorexceptionsyntax error
What information is required for a complete citation of a website source?A: the title, volume number, and page numbersB: the responsible person or organization and the website URLC: the responsible person or organization, date accessed, and URLD: the responsible person or organization and the date accessed
What qualities or characteristics of your teammates are important to the success of the team?
Once a device has failed, what metric measures the average amount of time to repair?a.mean field replacement time (MFRT)b.mean time to repair (MTTR)c.mean time to restore (MTTR)d.mean restoration time (MRT)
_________ help(s) prevent a person from being a single point of failure.

Create a query that will list all technician names, employee numbers, and year hired in order by year hired (Newest to Oldest).

Answers

Answer:

SELECT TECHNAME, EMPNUM, YEAR FROM EMPLOYEE ORDER BY YEAR DESC

Explanation:

The table definition is not given;

However, I'll make the following assumptions

Table Name:

Employee

Columns:

Technician name will be represented with Techname

Employee number will be represented with Empnum

Year Hired will be represented with Year

Having said that; the sql code is as follows:

SELECT TECHNAME, EMPNUM, YEAR FROM EMPLOYEE ORDER BY YEAR DESC

The newest year hired will be the largest of the years;

Take for instance:

An employee hired in 2020 is new compared to an employee hired in 2019

This implies that the year has to be sorted in descending order to maintain the from newest to oldest.

An attempt to generate a large number of session IDs and have a server process them as part of a session hijack attempt is known as what type of attack

Answers

Answer:

An attempt to generate a large number of session IDs and have a server process them as part of a session hijack attempt is known as

TCP Session Hijacking.

Explanation:

TCP Session Hijacking is a cyber-attack in which illegitimate access is acquired to a client's server in the network.  The attacker then hijacks the TCP/IP session by reading and modifying transmitted data packets and also sending requests to the addressee's server.  To achieve this attack effectively, the hacker generates a large number of session IDs, thereby confusing the client's server to process them as a part of the users' sessions. Sessions (a series of interactions between two communication end points) are used by applications to store user parameters and, they remain alive until the user logs off.

Which of the following are key corporate assets?A) intellectual property, core competencies, and financial and human assetsB) production technologies and business processes for sales, marketing, and financeC) knowledge and the firm's tangible assets, such as goods or servicesD) time and knowledge

Answers

Answer:

A) intellectual property, core competencies, and financial and human assets                                

Explanation:

Key corporate assets are

Intellectual property

Core competencies

Financial and human assets.

Corporate assets are referred to as individuals, properties, goods, data  company or firm repute.These assets are managed digitally. A digital firm is the one in which almost all the important business partnerships and relationships that an organization has with their employees, customers are administered, interposed and handles digitally.

Intellectual property:

It is a property that is the outcome of human creativity and intelligence. It is an intangible property such as copyrights, patents, trademarks etc. The IP strategy is basically a strategy, in accordance with the company's business objectives, to obtain IP assets and extract the most benefit from current IP assets.

Core Competencies:

Core competencies are the skills and proficiency that are essential for a company or business to attain competitive edge. They separate an organization from its competitors and create a competitive lead for a it in the marketplace. Core competency is an corporation's tactical and strategic strength. Development of core competencies of an corporation helps to sustain the competitive advantage of the corporation for a long time.

Financial and human assets.

Basically, the individuals in a corporate determine and define a corporate's success or failure. Human assets are a part of the company's intangible assets. For example human capital is an intangible asset. It can be defined as economic benefit of a worker's experience and skills. For example assets like knowledge, training, intellect, expertise, health. The abilities of employees reflects corporate's assets.

Financial assets refer to a security contract that contains a right over the real assets of a company. For example cash, stocks, bonds and bank deposits. A financial asset has a claim on the real assets or physical assets usually possessed by a company. Financial assets 'main contribution is to finance companies or money making organizations. These are provided in the market so that investors can bring their investments to use, and corporations can invest in real assets and make money.

Please explain in 2-4 sentences why diligence is needed and is important in building a pc. Thank you

Answers

Diligence is required for a variety of reasons. I’m going to give you two. Remember, when you’re building a PC, you’re handling hundreds of dollars worth of hardware that are also very fragile (a cord could make all the difference). Two, you need to know and understand how to make a PC. If you have no idea how to build one, RESEARCH FIRST.

Hope this helps.

In the early days of computer technology, which system was justified because data-processing personnel were in short supply, hardware and software were expensive, and only large organizations could afford computers

Answers

Answer:

Centralized Processing

Explanation:

Centralized processing was developed to process all of the data in a single computer, and since the first computers were stand-alone with all input and output devices in the same room, only the largest organizations could afford to use centralized processing.

Write a program to provide information on the height of a ball thrown straight up into the air. The program should request as input the initial height, h feet, and the initial velocity, v feet per second. The height of the ball after t seconds is

Answers

Answer:

The height of the ball after t seconds is h + vt - 16t 2 feet:

def main():

getInput()

def getInput():

h = int(input("Enter the initial height of the ball: ")) # Adding the int keyword before input() function

v = int(input("Enter the initial velocity of the ball: ")) # Same as above

isValid(h,v)

def isValid(h,v):

if ((h <= 0) or (v <= 0)):

print("Please enter positive values")

getInput()

else:

maxHeight(h,v)

def maxHeight(h,v):

t = (v/32)

maxH = (h + (v*h) - (16*t*t))

print ("\nMax Height of the Ball is: " + str(maxH) + " feet")

ballTime(h, v)

def ballTime(h,v):

t = 0

ballHeight = (h + (v*t) - (16*t*t))

while (ballHeight >= 0):

t += 0.1

ballHeight = (h + (v*t) - (16*t*t))

print ("\nThe ball will hit the ground approximately after " + str(t) + " seconds")

# Driver Code

main()

Answer:

I am writing a python code.

def getInput():

   h = int(input("enter the height: "))

   v = int(input("enter the velocity: "))

   isValid(h,v)    

def isValid(h,v):

   if (h<= 0 or v<=0):

       print("not positive ")            

   else:

       height = maximumHeight(h,v)

       print("maximum height of the ball is", height," ft.")

       balltime = ground_time(h,v)

       print("The ball will hit the ground after", balltime, "s approximately.")

def maximumHeight(h,v):

   t = (v/32)

   maxheight = (h + (v*t) - (16*t*t))

   return maxheight    

def ground_time(h,v):

   t = 0.1

   while(True):

       heightofball = (h + (v*t) - (16*t*t))

       if (heightofball <= 0):

           break

       else:

           t += 0.1  

   return t

Explanation:

There are four functions in this program.

getInput() function is used to take input from the user which is height and velocity. h holds  the value of height and v holds the value of velocity. input() function is used to accept values from the user.

isValid() function is called after the user enters the value of height and velocity. This function first checks if the value of height and velocity is less than 0. If it is true the message not positive is displayed. If its false then maximumHeight() is called which returns the maximum height of the ball and function ground_time() is called to return the time when the ball will hit the ground.

maximumHeight() function first divides the value of velocity with 32 as the ball will reach its maximum  height after v/32 seconds. It then returns the maximum height by using the formula:  heightofball = (h + (v*t) - (16*t*t)).

ground_time() calculates the time the ball takes to reach the ground. There is a while loop to height after every 0.1 second and determine when the height is no longer a positive. It uses (h + (v*t) - (16*t*t)) formula to calculate the height and when the value of height gets less than or equal to 0 the loop terminates otherwise it keeps calculating the height while adding 1 to the value of t at each iteration. After the loop breaks, it returns the value of t.

To see the output of the maximum height and time taken by ball to reach the ground, you can call the getInput() function at the end of the above program as:

getInput()

Output:

enter the height: 9

enter the velocity: 10

maximum height of the ball is 10.6525  ft.

the ball will hit the ground after 1.2 s approximately.