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
jenyasd209 [6]
3 years ago
13

Write down a recurrence relation for this version of QuickSort, and solve it asymp-totically. Show your work. Assume that the ti

me it takes to find the pivot (eitherbest or worst, depending on the level of recursion) is Θ(n) for lists of lengthn.
Computers and Technology
1 answer:
torisob [31]3 years ago
5 0

Answer:As in merge sort, the time for a given recursive call on an n-element subarray is Θ(n). In merge sort, that was the time for merging, but in quicksort it's the time for partitioning.

Explanation:

Worst-case running time:

When quicksort always has the most unbalanced partitions possible, then the original call takes cncnc, n time for some constant ccc, the recursive call on n-1n−1n, minus, 1 elements takes c(n-1)c(n−1)c, left parenthesis, n, minus, 1, right parenthesis time, the recursive call on n-2n−2n, minus, 2 elements takes c(n-2)c(n−2)c, left parenthesis, n, minus, 2, right parenthesis time, and so on. cn+c(n−1)+c(n−2)+⋯+2c=c(n+(n−1)+(n−2)+⋯+2)

=c((n+1)(n/2)−1)

The last line is because 1 + 2 + 3 +...... n is the arithmetic series

Best-case running time:

Quicksort's best case occurs when the partitions are as evenly balanced as possible: their sizes either are equal or are within 1 of each other. The former case occurs if the subarray has an odd number of elements and the pivot is right in the middle after partitioning, and each partition has (n-1)/ 2 elements. The latter case occurs if the subarray has an even number n of elements and one partition has n/2 elements with the other having n/2-1.In either of these cases, each partition has at most n/2 elements.

Using big-Θ notation, we get the same result as for merge sort: Θ(nlog2n)

You might be interested in
An attacker has obtained the logon credentials for a regular user on your network. Which type of security threat exists if this
jarptica [38.1K]

Answer:

privilege escalation.

Explanation:

An access control can be defined as a security technique use for determining whether an individual has the minimum requirements or credentials to access or view resources on a computer by ensuring that they are who they claim to be.

Simply stated, access control is the process of verifying the identity of an individual or electronic device. Authentication work based on the principle (framework) of matching an incoming request from a user or electronic device to a set of uniquely defined credentials.

Basically, authentication and authorization is used in access control, to ensure a user is truly who he or she claims to be, as well as confirm that an electronic device is valid through the process of verification

Hence, an access control list (ACL) primarily is composed of a set of permissions and operations associated with a user account or new technology file system (NTFS) file such as full control, read only, write, read and execute and modify.

In this scenario, an attacker or hacker was able to obtain the logon credentials for a regular user on your network. Thus, the type of security threat which exists if this user account is used by the attacker or hacker to perform administrative functions is privilege escalation.

Privilege escalation can be defined as a network or security threat which involves the exploitation of a design flaw, bug or unsecured configuration settings in a software program (application), operating system (OS), computer system, etc., so as to have an unauthorized access and gain more permissions, elevated rights or privileges that are normally protected from a user account or software program.

Hence, when an attacker or malicious user such as a hacker gains an unauthorized access to the privileges of another user account beyond what is intended or entitled to a user, it is known as privilege escalation.

6 0
3 years ago
Select the correct answer from each drop-down menu. Rita runs a small business that designs custom furnishings for corporate cli
LUCKY_DIMON [66]

Software as a Service cloud model is ideal for Rita’s business. SaaS are office solutions that allow Rita’s small business to work more efficiently and in a more organized way. Most SaaS applications are used for invoicing and accounting, sales, performance monitoring, and overall planning. SaaS applications can save Rita money. They do not require the deployment of a large infrastructure at her location. As a result, it drastically reduces the upfront commitment of resources. Whoever manages SaaS’s IT infrastructure running the applications brings down fees for software and hardware maintenance. SaaS has generally been acknowledged to be safer than most on-premise software.

5 0
3 years ago
Read 2 more answers
A series of inventions led to the creation of the electronic digital computer shortly after this war..
lesantik [10]
What is world war 2? bob
4 0
3 years ago
Is the disk in the C: drive fixable or removable disk
katrin2010 [14]

Answer:

The disk is a removable disk.

8 0
3 years ago
Read 2 more answers
Linux distributions automatically come with a native software firewall.TrueFalse
Elodia [21]

Answer:

False.

Explanation:

Ubuntu which is an linux distribution and it is based on debian. Ubuntu does not come with automatic firewall and we also have to manually enable the firewall after installing it otherwise it will be disabled.

You can control the firewall from a graphical interface.

Hence the answer to this question is False.

3 0
3 years ago
Other questions:
  • A __________ is the column of data in a database that is used as the basis for arranging data.
    8·2 answers
  • What filter gives a “squeezed” effect to an image?
    14·2 answers
  • If there are no differences between the amino acid sequences in the cytochrome c protein of humans and chimpanzees why aren't we
    15·1 answer
  • Which mistakes are NOT highlighted by the spell checker in a word-processing document?
    15·2 answers
  • Suppose that outfile is an ofstream variable and output is to be stored in the file outputData.out. Which of the following state
    15·1 answer
  • If you wanted a smartphone with the fewest restrictions on application development which smartphone operating system should you
    9·1 answer
  • Q.drtrdyudoijoemrkdf
    6·2 answers
  • Which type of information should never be given out on social media?
    5·2 answers
  • A database that is created and maintained using services such as Microsoft Azure or Amazon AWS is called a(n) _____ database.
    7·1 answer
  • How do you declare variables in c program
    14·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!