SRL Archive - General

Can somebody take a look at these sorting algorithms and tell me, or at least point me in the right direction, to how to count the worst case scenario. (Big0)

Here are the classes

Merge Sort : http://pastebin.com/8Nze6c7w
Quick Sort : http://pastebin.com/HFfK7W0R


Here is an example of what I mean
Insertion Sort : http://pastebin.com/WB4ns9fr

Assuming this is for a class, what kind of proof do you need?

I ask because there is no way to determine big-O in all cases, so the assignment depends almost entirely on what your teacher is requiring you to do. However, to aid you in your endeavor, realize that what you are basically trying to do is find a formula that describes the number of logical choices (if statements or other comparisons) that the program will encounter in the worst case (if there are multiple execution paths, one being O(1) and the other O(n^2), the algorithm is the second).

I would suggest that you draw out a flow chart, and run some sample data through it, counting the number of if statements you encounter in your runthrough.



As an aside, realize the limitations of Big-O notation: the bubble sort, seen as the worst one, has the same Big-O as shell sort – O(n^2).

From: R0b0t1
Assuming this is for a class, what kind of proof do you need?

I ask because there is no way to determine big-O in all cases, so the assignment depends almost entirely on what your teacher is requiring you to do. However, to aid you in your endeavor, realize that what you are basically trying to do is find a formula that describes the number of logical choices (if statements or other comparisons) that the program will encounter in the worst case (if there are multiple execution paths, one being O(1) and the other O(n^2), the algorithm is the second).

I would suggest that you draw out a flow chart, and run some sample data through it, counting the number of if statements you encounter in your runthrough.



As an aside, realize the limitations of Big-O notation: the bubble sort, seen as the worst one, has the same Big-O as shell sort – O(n^2).

Here's the assignment description

http://faculty.kirkwood.edu/pdf/uploaded/262/cs2/sp13/Program%202SortingAnalysis.pdf

http://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities

With that general idea in mind (from the link), I think the critical sections may refer to something your instructor mentioned in class, or perhaps it may refer to the sorting comparisons being done within each algorithm, and increasing a count when elements are compared. Thus giving an idea of ratio to other sorting methods for a constant element array amongst all sort methods. Granted it looks like your instructor wants it a constant randomized array, a constant low to high array, and a constant high to low array.

That's my interpretation, given my horrid elaboration.

A summary of your results; this should include the average number of critical section runs for
each of the different size N arrays you tested, and your analysis as to the algorithm’s performance –
did it work as advertised? Was it better or worse?

The total runtime for the merge procedure, a component of the sort, will be
Tm(n, m, p) = sum[q, i, 0, m/2] + sum[q, i, 0, m/2] + sum[q, i, 0, m/2] (q is the variable of comparison)
Tm(n, m, p) = 3*sum[q, i, 0, m/2]
Tm(n, m, p) = 3*(m/2)*q
Tm(n, m, p) = q = "n"
therefore merge(n, m) ? O(n)

The total runtime of the merge sort will be
Ts(n, m) = Ts(n, m/2) + Ts(n + (m/2), (n - (m/2)) + Tm(n, m, p)
with a base case of
Tsb(n, m) = q where m <= 1.
The base case results in one comparison (quantity of time).

Ts(n, m) = Ts(n, m/4) + Ts(n + (m / 4), (n - (m/4)) + q + Ts(n + (m/2), (n - (m/2))/2) + Ts(

the first part looks like
sum[Ts(n, m*(1/2)^i) + Ts(n + m*(1/2)^i, n - m*(1/2)^i) + q, i, 0, ???]
sum[Ts(n, m) + Ts(n, m) + q, i, 0, ???]
sum[q + q + q, i, 0, ???]
3*???*q
q = "n"

the second like
sum[Ts(

…. Nevermind I fucked up, here's a powerpoint. http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/04MergeQuick.pdf

Page 3.

And this https://en.wikipedia.org/wiki/Master_theorem